Mail devuelve true si es exitoso y false si no (lo digo por que no lo has comprobado).
Si funciona, Mail asegura que intentará enviarlo, pero no que llegará al destino. Si quieres puedes usar el Módulo de PEAR de Mail, o el mío (
http://anesgysd.byethost7.com/Clase-AMailer-PHP-.html) para enviar por SMTP el correo. Si hay un fallo en el envío la propia conexión SMTP te lo dirá, y si el destinatario está mal colocado, entonces el servidor de correo se encargará de devolverte el mensaje.