I'm sorry but i don't agree with Randy, I have experienced this before and as you can send internally I dont think that its an exchange problem.
From memory I fixed this problem by making sure that the headers you submit to the server are in the correct format and that there is a default address/user specified in the php.ini file.
Dont worry what you set in the php.ini file as you can easily overide it by setting the from info in the header info.
eg
$header = "From: nobody@home.com\n Reply-To: me@home.com"
$to = "someone.else@hotmail.com";
$message = "You should know what goes here!";
$subject = "Blah Blah";
$send_result = mail( $to, $subject, $message, $header );
// ofcourse the reply to is optional, but for reliable operation I have found that
// you must alteast have a from address.