Problemas con envío de mail

[codify]

Hola,

Estoy intentando hacer un envío de mail con la funcion mail() de PHP y cuando el envío es a una cuenta de gmail llega sin problemas pero cuando envío a una otra cuenta tipo outlook, hotmail u otro destinatario el envío se hace correctamente pero no llega a ningún lado.
He mirado si se daba el caso de que fuera a la carpeta de SPAM pero no, ahí tampoco está.

El código usado es el siguiente:
$cabeceras = "MIME-Version: 1.0"."\r\n";
$cabeceras .="Content-type: text/html; charset=iso-8859-1"."\r\n";
$cabeceras .="To: ".$email."\r\n";
$cabeceras .="From: [email protected] <[email protected]>"."\r\n";
$cabeceras .= "Sensitivity: Personal\n";

$body = $body;
$para = $email;
$asunto = "xxxxxxxxx";
mail($para, $asunto, $body, $cabeceras);

Cambiar las xxx por textos coherentes, claro

Gracias a quien pueda echarme una mano...

[codify]

Por lo que puedo comprobar usando PHPMailer me pasa exactamente lo mismo:
// ------------------------------------------------------------------

require("includes/PHPMailer_5.2.1/class.phpmailer.php");

$mail = new PHPMailer();
$mail->Host = "localhost";
$mail->From = "[email protected]";
$mail->FromName = "xxxxxxxxxxx";
$mail->Subject = "xxxxxxxxxxxxxxxxxxxxxxxx";

$mail->AddAddress($email);
$mail->Body = $body;
$mail->IsHTML(true);
$mail->Send();

// ------------------------------------------------------------------