Verifique se o registro MX do servidor de e-mail está se referindo tem registro A, CNAME não é suficiente. Isso é importante, mas não me lembro por quê. Aqui está um exemplo:
$ORIGIN example.com.
@ IN SOA dns0.yourisp.com. zone.yourisp.com. 1308717736 21600 7200 1209600 10800
@ IN NS dns1.yourisp.com.
@ IN NS dns2.yourisp.com.
@ IN MX 10 mail.example.com.
mail IN A 192.168.1.200
...
Além disso, verifique se há um registro PTR correspondente que resolva endereços IP para o nome do seu servidor de e-mail. Isso não está diretamente relacionado ao seu problema, mas é importante para a entrega bem-sucedida de e-mails.
$ORIGIN 1.168.192.IN-ADDR.ARPA.
@ IN SOA dns0.yourisp.com. zone.yourisp.com. 2011041900 3h 15m 3w 3h
@ IN NS dns1.yourisp.com.
@ IN NS dns2.yourisp.com.
200 IN PTR mail.example.com.
...
Depois de ter seu e-mail funcionando, considere adicionar o registro SPF .