Existem muitas possibilidades envolvidas com esse erro. Retirado de esta minha resposta em outra pergunta (mas ligeiramente modificada) :
Primeiro, tente estabelecer uma sessão SMTP com os servidores de e-mail remotos usando o telnet para ver se você pode obter mais informações.
Também é possível que algum tipo de regra de firewall excêntrica tenha sido definida para eliminar, alterar ou, de outra forma, ajustar pacotes para ou de um domínio ou IP associado ao servidor remoto. Improvável, mas eu vi coisas estranhas. Verifique o firewall do seu gateway, bem como o firewall de software do servidor Exchange, quanto a qualquer regra que possa ter algo a ver com o servidor SMTP remoto. Verifique se há domínios, IPs e qualquer intervalo de endereços que possam estar associados ao domínio remoto.
Outra possibilidade é que o domínio remoto tenha problemas de zona DNS. Talvez seus registros MX estejam obsoletos. Talvez eles tenham realizado uma migração de zona, mas nunca migraram tudo para o novo servidor DNS. Mais uma vez, coisas mais loucas aconteceram.
Outra possibilidade é que o servidor de recebimento esteja realizando uma pesquisa reversa de DNS no IP de envio e não esteja correspondendo aos registros MX. Se o seu registro MX apontar para 192.0.2.1, mas estiver atrás do firewall 192.0.2.2 e um IP virtual estiver configurado no firewall para aceitar 192.0.2.1, o tráfego de saída será visto como 192.0.2.1, mas o RDNS será mostre 192.0.2.2 como o servidor de correio. Essa discrepância pode fazer com que alguns servidores de recebimento rejeitem a mensagem de várias maneiras (embora eu espere que o administrador de email do destinatário não suprima mensagens de devolução informativas, optando por mensagens de falha genéricas).
(Como uma nota lateral, as verificações de RDNS como as descritas acima são tolas já que muitas pessoas autenticaram retransmissões para emails de saída e que, por necessidade, não corresponderão ao servidor de entrada. Administradores de email, não sejam preguiçosos!)
Por último, mas certamente não menos, USE SPF RECORDS! DKIM também. Você pode descobrir que muitos dos seus problemas de e-mail temporários simplesmente desaparecem depois de configurar corretamente essas duas coisas.Claro, ouça Shane Madden e verifique sua fila de e-mails .
No final, entre em contato com os administradores do domínio remoto e trabalhe com eles . Você pode ter que trabalhar com eles para descobrir o problema.