Bueno .. lo que te decía antes .. Estas usando muyyyyyyy pocas (por no decir nada) de las cabeceras standars de mail (del protocolo SMTP para mail) .. Puedes ver más de estas cabeceras en la própia documentación de PHP:
http://www.php.net/manual/en/function.mail.php
Personalmente para no complicarme con los "RFC's" que definen el protocolo SMTP . .yo uso la classe:
PHP Mailer
http://phpmailer.sourceforge.net
Implementa parte (bastante) del protocolo SMTP (cabeceras y otros detalles) para que tu e-mail sea lo más standard posible. (Además de permitirte enviar el e-mail vía mail() de PHP .. o por SMTP directo entre otros)
Un saludo,