Lo mas seguro que le dijeron CGI por que su hosting no tiene la funcion mal, le recomiendo bajar el script PHPMailer(); para enviar correos, hay varios ejemplos y es muy simple e intuitivo.
1.- necesita la libreria PHPMailer(); la puede bajar de
aqui
2.- tener una cuenta real de correo activa
3.- configurar a gusto
Te dejo un link donde explican como configurar y usar PHPMailer paso a paso es cosa de dedicarle un poco de tiempo si no entiende algo nos avisa, pero no es cosa de agregar todo el código y decir me falla el código, el codigo cuando falla siempre viene con algun error de la mano el cual nos hace la tarea mas facil
http://blog.unijimpe.net/introduccion-a-phpmailer/