Vas a tener problemas de todo tipo con los CSS: primero no te los toma inline con style="" y despues los <p> en Yahoo!
Te dejo algo que hice:
Código PHP:
<?php
$msg ="Mensaje de prueba";
$template = <<<EOF
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<title>{title}</title>
<style type="text/css">
body { font-size: 12px; margin: 0; padding: 0; font-family: Georgia, Times New Roman, Times, serif; }
p { font-size: 14px; color: #333333; margin-top: 0px; margin-bottom: 12px; padding: 0; font-family: Arial, Helvetica, sans-serif; }
h1 { color: #fff; font-size: 21px; font-family: Arial, Helvetica, sans-serif; margin: 0; padding: 0; text-shadow: 1px 1px 1px #000; }
.content p { font-size: 14px; color: #333333; margin-top: 0px; margin-bottom: 12px; padding: 0; font-family: Arial, Helvetica, sans-serif; }
.header h1 { font-family: Arial, Helvetica, sans-serif; font-size: 42px; margin: 0; padding: 0; color: #0d2d42; text-shadow: 1px 1px 1px #fff; }
.footer p { font-size: 12px; color: #666; margin: 0; padding: 0; font-family: Arial, Helvetica, sans-serif; }
ul { margin: 0; padding-left: 14px; line-height: 18px; list-style: disc; }
li { font-family: Arial, Helvetica, sans-serif; font-size: 12px; color: #00ffff; font-weight: bold; margin: 0; padding: 0; }
</style>
</head>
<body style="margin: 0; padding: 0; background-color: #d8e7ea;" marginheight="0" topmargin="0" marginwidth="0" leftmargin="0">
{simple body}
</body>
</html>
EOF;
$to= $_GET['to'];
$from= $_GET['from'];
$subject = "Bienvenida ".rand(20000,50000);
// To send HTML mail, the Content-type header must be set
$headers = 'MIME-Version: 1.0' . "\n";
$headers .= 'Content-type: text/html; charset=iso-8859-1' . "\n";
// Additional headers
//$headers .= "To: $to" . "\r\n";
$headers .= "From: $from" . "\n";
$msg = "Hola amigo<p/>Como estas ? este es un correo de notificacion ";
$msg = str_replace('{simple body}',$msg,$template);
$msg = str_replace('{title}','Pagina de prueba',$msg);
echo $msg;
//Mail it
//echo "FROM: $from<br/>TO: $to<br/>SUBJECT: $subject<p/>$msg";
$e = mail($to, $subject, $msg, $headers);
var_dump ($e);
?>