Well you've obviously won half the battle already because the MX records are working or you wouldn't be seeing this mail. The reason the mail is being rejected is because you have anti-relaying rules in place. Assume for a moment that the name of the domain in question is hisdomain.com and add the following to /etc/mail/access:
hisdomain.com RELAY |
Now issue the command makemap hash /etc/mail/access.db < /etc/mail/access, restart sendmail and try your tests again. Do not add hisdomain.com to class w or sendmail.cw on your machine!