Isso funcionou para mim no Outlook 2010.
Na caixa de entrada da pesquisa (na parte superior da sua lista de mensagens Ctrl + E), digite ..
category:Work category:Germany
Estou usando as categorias do Outlook para enviar e-mails e entrar em contato com a turma.
Existe uma maneira de pesquisar na categoria da mesma maneira que no GMail?
Algo como "categoria = trabalho e categoria = Alemanha".
Embora 'funcione' para pesquisar por "categoria" sem os dois pontos, isso na verdade não encontra todos os documentos marcados com QUALQUER categoria, para mim. No entanto, isso faz o truque: "followupflag: followup flag". Também é possível adicionar uma palavra de subconjunto para pesquisar depois dessa frase.
Acompanhei esta resposta enquanto pesquisava uma questão relacionada para mim. Além das informações fornecidas pelas outras duas respostas, existem TONELADAS de excelentes dicas de pesquisa para o Outlook neste link. (incluindo como realizar pesquisas OR ou restringir vários critérios, incluindo pesquisas de tempo relativo, como "de: Bossman E recebido: último mês")