I had this too, drove me nuts, until I included the headers and an f flag:
$to = "recipent@emailaddress.org.uk";
$from = "-fwebmaster@mydomain.org.uk";
$subject = "feedback from Website";
$msg = "test message";
$mailheaders = "MIME-Version: 1.0\r\n";
$mailheaders .= "Content-type: text/html; charset=iso-8859-1\r\n";
mail ($to, $subject, $msg, $mailheaders, $from);
then it worked
the $to or the $from needed to be from my domain aswell
Julia