Frequently, Internet hosts will have trouble getting mail into misconfigured remote sites. There are several variants of this problem, but the general symptom is that mail is bounced by the remote system or never gets there at all.
These problems can put the local system administrator in a bad position because your users generally don't care that you don't personally administer every system worldwide (or know how to get the remote administrator to fix the problem). They just know that their mail didn't get through to the desired recipient on the other end and that you're a likely person to complain to.
A remote site's configuration is their problem, not yours. In all cases, be certain to not break your site in order to communicate with a misconfigured remote site. If you can't get in touch with the Postmaster at the remote site to get them to fix their configuration in a timely manner, you have two options.
You can fix the bad headers in the envelope on your outgoing messages only by using a domaintable entry for their host/domain that results in the invalid information being corrected in mail originating from your site:
The ! in the following mailertable delivers mail to their remote site making it appear to their sendmail as if it had originated locally on their system. Note that this changes only the envelope address, so the proper return address will still show up in the message.
Regardless, even if you get mail into their system, there is no guarantee that they can reply to your message (they're broken, remember...) but then their users are yelling at their administrators rather than your users yelling at you.