Isso parece um problema de DNS no seu envio MTA. Você já tentou enviar e-mails de teste de outros provedores, como o Gmail?
# host msn.com
msn.com has address 65.55.206.228
msn.com mail is handled by 5 mx3.hotmail.com.
msn.com mail is handled by 5 mx4.hotmail.com.
msn.com mail is handled by 5 mx1.hotmail.com.
msn.com mail is handled by 5 mx2.hotmail.com.
# host -t A msn.com
msn.com has address 65.55.206.228