O problema é que os registros de descoberta automática do outlook devem apontar para o servidor de troca local até que o último usuário seja migrado dele. O servidor de troca local está fazendo o redirecionamento de descoberta automática para caixas de correio que estão na nuvem do O365.
A confusão que aconteceu é que o O365 dá um aviso de que os registros DNS estão incorretos. É por isso que a minha descoberta automática apontava para o O365. Eu pensei que servidores O365 farão o redirecionamento para as caixas de correio locais. Eu estava errado.