Primeiro verifique como seus MX'es estão definidos: host -t mx yourdomain.com. E, em seguida, verifique se você pode telnet mail.yourdomain.com 25 de fora para ver se você pode se conectar à porta SMTP bem.
Parece-me que o MTA está ligado ao localhost ou que você tem algum firewall bloqueando o acesso SMTP.