O DNS reverso está configurado para o IP de saída dos e-mails?
Alguns servidores de e-mail (principalmente os grandes provedores) possuem validação de DNS reverso, e se ele não estiver configurado, as mensagens não vão chegar mesmo.
Você pode testar da seguinte forma:
No prompt de comando digite:
ping -a 189.xxx.xxx.xx1 (endereço de IP do seu servidor)
Se o reverso estiver configurado, ele vai aparecer "Disparando mail.seuhostname.com [189.xxx.xxx.xx1]" na primeira linha depois que você der um ENTER.
Para o DNS Reverso funcionar perfeito, o hostname mail.seuhostname.com PRECISA responder para o endereço de saída de e-mails (o primeiro que a gente testou), ou seja:
ping mail.seudominio.com (hostname do reverso)
Resposta de 189.xxx.xxx.xx1
Se eu não me engano, o hostname do servidor precisa ser igual ao DNS reverso configurado!
Alguém me corrija se eu estiver errado.
Espero ter ajudado!
Abraço!