No compruebas si mail tuvo éxito. A ver mail devuelve true si tiene éxito y false si no. Prueba a empezar con esto.
Me imagino que habrás comprobado las direcciones, pero por si ves que no te sale, puedes usar SMTP.
Para conectarte con SMTP puedes usar el módulo de PEAR Mail, o mi módulo
http://anesgysd.byethost7.com/Clase-AMailer-PHP-.html, o cualquier otro módulo de envío por SMTP. De esta forma si envías por SMTP puedes ver si el correo es devuelto (es decir si no existe el destinatario).
Empieza primero por comprobar mail, pero recuerda que mail es una función algo lenta y por tanto a lo mejor tarda media hora en llegar el correo.