Yo he alojado en miarroba y he utilizado la funcion mail para enviar correos y siempre han llegado.
$mail : direccion "PARA"
Código PHP:
if (mail($mail,"Mensaje desde la Web",$body,"From: [email][email protected][/email]") ) echo "Mensaje enviado OK";
else echo "Mensaje no Enviado";
si así escribiste la funcion mail no veo motivo para que no te funcione
salu2!