Pues por lo que tengo entendido, el problema de la función mail(), es que necesitas que el serivodor SMTP, este instalado en tu ordenador,sitio...
Si tienes contratado un serividor como parece ser tu caso, lo mejor es que utilices una clase alternativa, como PHPMailer().
Aquí te dejo un enlace que explica muy bién cómo se utiliza:
http://www.programacion.net/php/articulo/phpmailer/
Además es más completa que mail().
Espero que te sirva.