Primeiro, verifique se a Pesquisa do Windows está ativada (Painel de Controle / Programas e Recursos / Ativar ou desativar recursos do Windows).
Em segundo lugar, verifique se a pasta do Outlook é usada em Opções do Outlook / Pesquisar / Fontes / Opções de indexação. Verifique se não há muitas outras pastas listadas, para minimizar o tamanho do índice.
Veja também este artigo .
Como outra otimização, você pode reduzir a parte do índice a pesquisar usando a Localização Avançada.
Outra solução seria usar um substituto de pesquisa para a pesquisa do Outlook, por exemplo, Xobni , Copernic ou Lookeen .
Outra alternativa costumava ser Lookout, que a Microsoft
comprado e enlatado, mas talvez esses artigos possam ajudar: Lookout: uma pesquisa poderosa função para o Outlook
Como instalar Lookout no Outlook 2007
Pesquisar e-mail no lightspeed: usando o Lookout com o Outlook 2007