Landen die Emails vlt. im Spamfilter?
Ansonsten:
Hinweis: [!] Bitte verwende nicht mail() sondern eine entsprechende Mailer Klasse! Viele Probleme lassen sich dadurch beheben.
Hier findest du einen Überblick von robo47 zu verschiedenen Mailer Klassen: Mail() ist tot, es lebe mail()