If the domain that he is replying to has multiple MX records for their domain, it is possiblt that most of the time he gets one server that is setup to receive the mail, and the other times he hits the other servers that are not setup to receive the mail.
Visit www.dnsstuff.com and complete a domain report for the domain in question. This will list the MX records for the domain. You can then telnet to these servers and test sending an email to see what messages you get back.
In case you need some telnet assistance:
http://support.microsoft.com/kb/153119