Occhio che mail non può garantire l'invio delle posta (specialmente su server linux dove ci si appoggia a sendmail). In quel caso la funzione mail passa la posta a sendmail ma se sendmail non è attivo o è configurato male non parte niente.
Se sei su winzoz invece non dovrebbero esserci problemi perchè php si collega in automatico ad un smtp.
Anche in quel caso cmq biosgna essere sicuri che l'smtp in questione accetti le tue mail (quasi tutti gli smtp effettuano dei controlli).
Cmq non ti consiglio di usare la funzione mail() di php.
Usa piuttosto qualche classe come phpmailer che ti permette di avere un certo controllo.

http://phpmailer.sourceforge.net