Esse é um comportamento esperado ao usar a conta do Exchange no Outlook 2016, pois o Outlook 2016 agora usa o Índice de Pesquisa do Exchange em prioridade para resultados de pesquisa mais consistentes em várias configurações do Outlook e aplicativos do Outlook (Web) Mail.
Para retornar o comportamento de pesquisa anterior que depende do Índice de Pesquisa do Windows, você pode definir o registro abaixo:
Chave: HKEY_CURRENT_USER \ Software \ Microsoft \ Office \ 16.0 \ Outlook \ Opções \ Pesquisa
Nome do valor: DisableServerAssistedSearch
Tipo de valor: REG_DWORD
Valor: 1
(Pode ser necessário criar manualmente a chave do registro para que ela não exista.)
Para sua referência (um artigo do fórum da MS Technet):
O Outlook 2016 agora usa o Índice de Pesquisa do Exchange em prioridade