Oye que raro vale, lo has probado con diferentes gestores de correo?... bien sea via web o desde windows?...
Eso esta bien extraño...
probastes colocandole los headers al mensaje?.. algo asi...
Código PHP:
<?
$headers = "MIME-Version: 1.0\r\n" ;
$headers .= "Content-type: text/html; charset=iso-8859-1\r\n";
$headers .= "From: TuEmpresa <[email protected]>\r\n";
//y colocarlo asi...
mail("$youremail", "$emailsubject", "$mailbody", "$headers"); // Enviar el email.
?>
Prueba nuevamente y avisas..
Saludos...