Mira no tanto es problema del hosting, aunque eso depende de como lo quieras ver, en mi opinion el problema es el método que usas ya que la función mail no hace envíos autenticados por lo que posiblemente le hosting tenga restringido ese tipo de envíos, yo siempre que necesito hacer envíos lo hago mediante phpmailer por lo que es la opción que podria recomendarte hay mucho ejemplos de como usarla en internet y en este foro por lo que si no la conoces hay basta información de su uso..
http://www.programacion.com/articulo..._phpmailer_213 http://www.forosdelweb.com/tags/phpmailer.html