Here is, how i did it... had kind of the same problem. We are using a Sun-Mail-Gateway.
Within our mail-domain everything worked fine... My linux-Box -> mail-gateway -> recipient...
All mails to "external" won't work...
until i've changed the header like this:
$headers = "MIME-Version: 1.0\r\n";
$headers .= "Content-type: text/plain; charset=ISO-8859-1\r\n";
$headers .= "From: $UserFullName <$sentby>\r\n";
if ($sendmeCC=='1'){$headers.="BCC: $sentby\r\n";}
$msubject=stripslashes(mb_encode_mimeheader($msubject, "ISO-8859-1", "Q"));
@mail("$sendto", $msubject , stripslashes($sendmsg), $headers, "-f$sentby");