intenta con cabeceras mejor definidas...
Código PHP:
Ver original<?php
// Para enviar un correo HTML, debe establecerse la cabecera Content-type
$cabeceras = 'MIME-Version: 1.0' . "\r\n";
$cabeceras .= 'Content-type: text/html; charset=iso-8859-1' . "\r\n";
// Cabeceras adicionales
// Enviarlo
mail($para, $título, $mensaje, $cabeceras);
?>
fuente.
http://php.net/manual/es/function.mail.php
Si con eso tampoco funciona, no te desanimes... todos hemos pasado por situaciones similares, prueba: registros SPF, domain.key... lo que te hemos recomendado, chekear IP en blacklist...