A questão principal aqui é o que aconteceu com o servidor Exchange antigo? A execução da Descoberta Automática nos clientes para apontar para o novo servidor não é suficiente - a Descoberta Automática não é uma coisa única. O cliente consultará a Descoberta Automática com freqüência e a primeira coisa que consultará será o domínio local do qual é membro. Isso é provavelmente o que está acontecendo aqui.
A correção dependerá do que aconteceu com o servidor Exchange antigo. Se ainda estiver ativo, alterar o registro interno de Descoberta Automática para apontar para o local externo deve ser tudo o que é necessário. Se o Exchange tiver sido removido, você verá alguns trabalhos adsiedit para remover o SCP para Descoberta Automática do domínio.