Si ya hicistes esas pruebas y nada... deberias probar el ejemplo propio de PHP.net:
Código PHP:
Ver original$titulo = 'El título';
$mensaje = 'Hola';
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.