Otro detalle que acabo de ver. Estamos enviando el e-mail en texto plano en lugar del html... Lo correcto sería:
En todo caso esto no solucionará el problema. ¿Has pensando en utilizar la clase phpmailer? Podrías ahorrarte muchos problemas y es muy fácil de utilizar.
¿El archivo php sólo tiene ese código? Es que parece estar bien y mail() devuelve true, por lo que parece que se envía... Pero no lo hace. ¿Estás probando desde el servidor o en local?