Passo a passo:

- realizar a checagem da indexação de itens restantes.

- em arquivo / opções / pesquisar / opções indexação, desative o Outlook

faça um teste, volte a habilitar e teste novamente,  fique com a opção que soluciona.

- ainda em opções de indexação / avançado, recrie o indice de indexação.


Sugestões para Outlook 2010: 

https://support.microsoft.com/pt-br/help/2647937

Sugestões para Outlook 2013/2016: 

https://social.technet.microsoft.com/Forums/pt-BR/0a7fb8bb-9155-48f3-8826-d8bb560f9ac6/pesquisa-instantnea-no-funciona-no-outlook-2013?forum=officept