Si ya hicistes esas pruebas y nada... deberias probar el ejemplo propio de PHP.net:
Código PHP:
Ver original$para = 'nobody@example.com';
$titulo = 'El título';
$mensaje = 'Hola';
$cabeceras = 'From: webmaster@example.com' . "\r\n" .
'Reply-To: webmaster@example.com' . "\r\n" .
mail($para, $titulo, $mensaje, $cabeceras);
ya si con este no funciona, ponte en contacto con tu proveedor de hosting, algunos deshabilitan la funcion mail() por el SPAM que causan otros usuarios o bien ponen ciertos requisitos que deben cumplir las cabeceras...
Lo del SMTP no tiene nada que ver ya que no estas autenticando.