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: