Te recomendaría usar los ejemplos textuales de php.net al respecto (uso de mail())
http://www.php.net/manual/en/function.mail.php
Y en su defecto ya que tienes tantos problemas con el uso de las cabeceras y demás .. podrías usar la classe:
PHP Mailer
http://phpmailer.sourceforge.net
Que es una mejora obstensible a mail() de PHP ..
Un saludo,