con la funcion mail() es muy dificil.
yo tenia ese problema hasta que vi la luz un dia.
PHPmailder me cambio la vida.
usa lo te lo recomiendo.
y por descargarlo ahora llebate una hermosa maquin.... perdon
me envole. jajaja
pd. para enviar con adjuntos:
http://phpmailer.worxware.com/index.php?pg=tutorial#3