L'email che non arriva verso quale dominio la invii?
Uno tra libero ed hotmail?

E' risaputo che questi due provider (forse anche altri) danno problemi.
Intanto prova ad usare PHPmailer per l'invio delle email, potrebbe già risolverti il problema.