Eu acho que isso é um problema de indexação - porque você está usando o IMAP você deve ter um arquivo OST (que está offline). É possível que não esteja sendo indexado. Para ver:
-
No menu Ferramentas, aponte para Pesquisa Instantânea e clique em Opções de Pesquisa (Como alternativa, clique na seta no painel Pesquisa Instantânea e clique em Opções de Pesquisa no menu).
-
Em Indexação, verifique se os arquivos de dados que você deseja incluir em sua pesquisa estão selecionados na lista de mensagens de índice nesses arquivos de dados.
Verifique também se a indexação está completa (no mesmo local).