Ich hatte das PHP-Problem Mail auch vor kurzem und bin auf eine Seite gestossen, die mir sehr weitergeholfen hat. Vielleicht ja auch dir...
http://www.dclp-faq.de/ch/ch-mail.html
Ansonsten hier mal mein Code, den ich daraus dann erstellt hatte:
$myname = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxx";
$myemail = "xxxxxxxxxxxxxxxxxxxxxxx";
$contactname = "xxxxxxxxxxx xxxxxxxxxxxxxx";
$contactemail = "xxxxxxxxxxxxxxxxxxxxxxxxxxx";
$message = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx";
$subject = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx";
$headers .= "MIME-Version: 1.0\r\n";
$headers .= "Content-type: text; charset=iso-8859-1\r\n";
$headers .= "From: ".$myname." <".$myemail.">\r\n";
$headers .= "To: ".$contactname." <".$contactemail.">\r\n";
$headers .= "Reply-To: ".$myname." <$myreplyemail>\r\n";
$headers .= "X-Priority: 1\r\n";
$headers .= "X-MSMail-Priority: High\r\n";
$headers .= "X-Mailer: Just My Server";
mail($contactemail, $subject, $message, $headers);