Tal vez mi respuesta no te ayude mucho, pero yo tengo el mismo
problemas con algunos dominios, pense que era un problema de DNS pero
al realizar pruebas no fue así, porque desde el mismo servidor me
conecte por telnet al servidor externo y pude enviarle un correo sin
problelmas, mas bien según lo que he leido pero aún no lo he podido
chequear por falta de tiempo es que ese problema se puede deber al
antivirus o al antispam que de alguna manera tienen registrado ese
dominio en las listas negras y lo único que tienes que hacer es
recrearla.
En un par de semanas voy a instalar mi servidor desde cero, en caso
solucione el problema te estaré comentando.
Salu2