La función mail() de PHP sólo te indica con un "true/false" (booleano) que PHP "pudo" concectar con el MTA (transportador) que use PHP (php.ini: SMTP = .. o sendmail= ....) para enviar el e-mail .. mejor dicho "para entregarselo", pero no de que si este (el MTA) pudo o no realizar el envio en sí (por qué falló .. no existe el domino o el usuario en ese servidor .. etc ...)
Así que lo más probable es que siempre te diga que el e-mail se "envió" por qué tu MTA siempre funcionó y tomó esos e-mails para enviarlos .. Ahora .. de que falle o no eso de momento sólo lo verías en los log de ese servidor SMTP o sendmail usado.
Para solventar el problema .. deberías enviar los e-mails directamente al SMTP y así controlar un poco mejor los mensajes de error que pueda dar y en consecuencia dedicir si el e-mail existe .. o simplemente fué un error de conexión temporal .. etc.
Para eso .. puedes usar classes como:
PHP Mailer
http://phpmailer.sourceforge.net
Pero .. en mis pruebas al menos (pese que dice que entrega dichos mensajes de error) no me los entrega :((((((((((( (algo no habré configurado bien o estaré usando lo mal o mi servidor SMTP no me devuelve esos errores? ..)
El caso es que "por ahí" va el tema para poder obtener dicha respuesta más exacta sobre el envio del e-mail.
Un saludo,