Hola rascabuchitos,
Hay que tener en cuenta que antes se enviaba sin ningún problema con la función mail(), pero ahora, la mayoría de los servidores lo envían de manera que llega al spam o directamente lo bloquean los sitios como spamcop y similares.
Yo te recomiendo hacer uso de la clase PHPMailer, funciona bastante bien y se puede personalizar casi todo.
Puedes echar un vistazo a este enlace:
http://www.desarrolloweb.com/articulos/phpmailer.html
Espero que te sirva.