No creo que pueda ser problema del hosting, pero no esta de mas revisarlo y consultar a tu proveedor.
Lo ultimo que podrias hacer es usar el
phpMailer, pero con SMTP, eso si te va ha descartar si tu host esta mal o no, por ejemplo:
http://blog.unijimpe.net/introduccion-a-phpmailer/ http://www.buayacorp.com/archivos/phpmailer-con-gmail/
Saludos