Eu estava tentando fazer o mesmo recentemente e, pesquisando na web, encontrei sua pergunta. Eu também não consegui encontrar nenhuma maneira de usar a pasta de pesquisa para verificar os cabeçalhos. Minha suposição é que os cabeçalhos da Internet não são realmente um "campo de troca", o que significa que não acredito em nenhum email de "intranet" enviado no próprio servidor do Exchange (como o email que você enviou com a foto do gato engraçado [LOLZ!]) seu colega de trabalho ...) tem esses cabeçalhos. Mas aqui está a solução que eu estou usando que estou usando.
Eu configurei uma nova regra no assistente de regras que, ao receber novas mensagens, verifique os cabeçalhos. Se uma string específica for encontrada, atribua a mensagem a uma categoria específica. No meu caso, estou procurando mensagens que vêm do nosso servidor Best Practical Request Tracker, em cada um desses cabeçalhos está a string "RT-ticket:". Se minhas regras encontrarem essa string no cabeçalho, elas atribuem a mensagem a uma categoria que eu criei chamada "RT Tickets". (Eu criei essa categoria sem cor, por isso é menos invasiva.) Posso criar uma pasta de pesquisa que procure mensagens de apenas essa categoria. Etapas extras, mas problema resolvido. Eu fiz isso no Outlook 2007, mas ele deve funcionar em qualquer versão do Outlook que ofereça suporte ao assistente de regras, verificando cabeçalhos e, em seguida, atribuindo categorias.
As desvantagens disso são 1) mais uma regra na minha lista crescente, e 2) se eu quiser aplicar isso aos emails já recebidos, precisarei passar e executar manualmente a regra em relação a essas pastas primeiro. Neste ponto, estou preocupado apenas com as novas mensagens atualmente na minha caixa de entrada ou com as que chegam daqui para frente, para que eu simplesmente defina a regra para ser executada no momento da criação e isso foi resolvido. Um benefício descoberto de usar as categorias é que você pode exibi-lo como uma coluna na sua lista de mensagens. Não tenho certeza se vou mesmo usar as pastas de pesquisa como pretendi, posso apenas classificar minha caixa de entrada por categoria para encontrar as mensagens desejadas.
Se alguém precisar das etapas de criação de uma regra expandida, basta deixar um comentário. Eu esperaria que, no entanto, se alguém é conhecedor o suficiente para estar cavando em cabeçalhos de e-mail na Internet que a criação de uma regra do Outlook seria old-hat. O assistente que eles têm é bem direto.