Vou tentar ser o mais claro e conciso possível, mas é um pouco confuso para mim.
Atualmente, minha empresa está hospedando um site em um servidor dedicado. Normalmente, manteríamos os registros DNS, mas o cliente para o qual estamos hospedando tem um servidor de correio externo que eles querem usar e decidiu que seria mais fácil ter um registro DNS externo. A configuração final é algo parecido com isto:
clientwebaddress.com para ns#.dnsrecordhost.com
O problema é que não podemos mais enviar e-mail para nosso cliente @ clientwebaddress.com porque nosso servidor da web também é nosso servidor de e-mail e está usando seus próprios registros como autoritativos. Tentamos apenas desativar nossos registros de DNS, mas isso não parece ajudar.
Estatísticas relevantes do servidor:
Deixe-me saber se deixei algo importante para fora. Honestamente, estamos em cima de nossas cabeças neste. Alguma idéia?
PS Quando digo "externo" acima, quero dizer externo ao nosso servidor web.
Seu servidor de e-mail deve estar usando o registro MX para rotear o e-mail. Configure um registro MX localmente para seu domínio e aponte-o para o servidor de email. Deve ser algo como mail.example.com em vez de example.com. Você precisa duplicar o registro A do servidor de e-mail.
Além da resposta do BillThor, também encerramos o serviço de e-mail para o domínio (quem configurou o domínio deve ativá-lo).