Directamente desde la función mail() de PHP no puedes ver si el correo ha llegado a su destinatario .. Dicha función te puede informar sólo si pudo contactar con el "transportador" (MTA, servidor SMTP..) para entregarle el e-mail que enviar .. pero el tramo desde ese MTA hasta la cuenta de correo del destinatario, si hay errores los informará ese servidor SMTP y si tu usas direccion de "Reply-to" o similares (no recuerdo si es esa exactamente) se te enviaran a donde indiques.
Para averiguar si una dirección de correo es válida (que exista ese usuario (lo que va antes del @) en ese servidor (@servidor.tal) y tal vez leer e interpretar el mensaje que te devuelva al intentar conectarte a ese servidor SMTP .. lo puedes hacer con Sockets y conexión directa enviando el e-amail por SMTP.
Algunas classes como:
PHP Mailer
http://phpmailer.sourceforge.net
te permiten enviar un e-mail usando conexiones SMTP directas y (creo) que gestionan el mensaje de error que te pueda devolver tipo "usuario no existe" y algunos otros mensajes de error.
Un saludo,