Bueno en el hosting tienen algo que se llama PEAR:
http://pear.php.net/
Lo he logrado hacer funcionar bien con este codigo:
include("Mail.php");
$recipients = " "; # Mail del receptor del correo
$headers["From"] = ""; # Cuenta de correo valida del dominio
$headers["To"] = ""; # Destinatario del correo
$headers["Subject"] = "Prueba"; # Asunto de mail
$headers["Reply-To"]=""; #Mail de respuesta
$mailbody = "Hola esto es una prueba."; # Cuerpo del mail
$smtpinfo["host"] = ""; # Servidor SMTP
$smtpinfo["port"] = "25";
$smtpinfo["auth"] = true;
$smtpinfo["username"] = ""; # Cuenta de correo para autentificar
$smtpinfo["password"] = ""; # Clave de la cuenta de correo
$mail_object =& Mail::factory("smtp", $smtpinfo);
$mail_object->send($recipients, $headers, $mailbody);
echo "el correo fue enviado";
Sólo me queda un pequeño detalle que quisiera cambiar. Cuando recibo el mail en el campo "De" veo la dirección de correo que coloco en $headers["From"] quisiera en lugar de ver la cuenta ver el nombre de la empresa (Nanatravel), es un detalle... Supongo que debe haber algún encabzado más para hacer esto pero no logro encontrarlo... ¿alguien tiene idea? Gracias!!