Descobrimos o que aconteceu. Ao mudar para usar o Exchange, todo o sistema para o qual a pesquisa parou de funcionar era aquele em que o cache do Exchange estava desativado. Aparentemente, a busca instantânea requer uma cópia local do email (não é de surpreender, suponho).
Eu entrei nas configurações da conta e liguei o cache local. Depois de baixar o e-mail e indexá-lo, a pesquisa instantânea começou a funcionar novamente.
Normalmente eu não respondo minhas próprias perguntas, mas como ninguém mais havia respondido, percebi que atualizaria isso caso alguém tivesse o mesmo problema.