Eu me deparei com o mesmo problema. O suporte disse que é apenas um problema de software. Eles mencionaram que pode haver um conflito entre o Office e o Lync. Eu completamente desinstalei o Office e o Lync; reinstalou o Lync; nada de bom. Eu completamente desinstalei o Office e o Lync; reinstalou o Office 2013 com o Lync; não é bom.
O que eu encontrei é uma ordem para executar os programas do Office. 1) Execute o Outlook. 2) Execute o Lync como administrador.
Se você fizer isso na ordem inversa, o Outlook exigirá que você o execute como administrador. Quando é executado como administrador, a funcionalidade de pesquisa não está mais disponível.
Acredito que o Lync esteja acessando os arquivos do Outlook e não tenha as permissões corretas. Isso leva aos conflitos e à execução do Lync como administrador.