Yo noté el mismo problema, pero solo en los correos de hotmail cuando el envio es por php o por cgi. en los demás nunca tube ese problema.
Los headders que uso son esotos:
Cita: //para el envío en formato HTML
$headers = "MIME-Version: 1.0\r\n";
$headers .= "Content-type: text/html; charset=iso-8859-1\r\n";
//dirección del remitente
$headers .= "From: noClip <
[email protected]>\r\n";
$enviar= mail($destinatario,$asunto,$cuerpo,$headers);