Estás usando la función mail() por casualidad? Para utilizarla no sólo tienes que usar la función mail, tienes que pasarle un servidor smtp. La función mail lo coge de php.ini. Allí tienes que configurar la dirección y el puerto de tu servidor SMTP, si no, nunca te funcionará.
Yo siempre la he usado con servidores de correo de empresas, pero si no tienes te he encontrado (no había más que buscar un poco) este
post, no lo he leído, pero igual te sirva.
Un saludo.