O problema foi resolvido. Esse era o problema: a Descoberta Automática foi alterada para apontar para o Exchange Online, enquanto alguns usuários ainda tinham algumas caixas de correio compartilhadas adicionadas manualmente em seu perfil de caixas de correio que nunca foram movidas para o Exchange Online.
Portanto, embora a resposta da Descoberta Automática não contivesse nenhuma referência a servidores locais, o cache do Outlook ainda tentava se conectar a um servidor local.
A remoção das caixas de correio "órfãs" dos perfis resolveu o problema.