in reply to Sending messages through exchange, originating in UNIX
A few options,
Fix your MTA issue like noted above.
Have the application that generates the email and does the processing live on a host that does not need to be obscured from the outside world -- an application server on a DMZ perhaps...
Fix your sendmail install to strip or obscure the first hop in such a way where your headers are not malformed causing the relay bounces -- correctly configured mail servers should accept those messages.
About your relaying issue, are you sending mail that is apparently from another domain than the one you are relaying through? Does that domains MX record include the relaying host? One of the only other reasons I can think of that the email is being anti-relay rejected is that your header rewrite is malformed.