O problema existe nos servidores de email do destinatário, não no seu lado. Verifique os registros MX dos domínios remotos e verifique se os servidores de e-mail estão respondendo às solicitações SMTP. Estabeleça uma sessão SMTP com os servidores de correio remoto 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 aponta para 0.0.0.1, mas está atrás do firewall 0.0.0.2 e um IP virtual está configurado no firewall para aceitar 0.0.0.1, o tráfego de saída será visto como 0.0.0.1, mas o RDNS será mostre 0.0.0.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 observação, as verificações de RDNS como as descritas acima são tolas, pois muitas pessoas têm retransmissões autenticadas para e-mails de saída e, por necessidade, não correspondem ao servidor de entrada. Os administradores de e-mail, não são preguiçoso! )
Por último, mas não menos importante, USE REGISTROS SPF < hk="http://www.dkim.org/"> 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.
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.