Lo que puedes hacer es verificar si el dominio de la cuenta de correo es un dominio valido y si tiene registros MX , la función
getmxrr te puede ayudar. ( Pero solo vas a saber si el domino es valido )
Ahora si no quieres enviar correos utilizando el mismo servidor (o el smtp configurado en el php.ini) puedes enviar correos utilizando otros smtp con PEAR:Mail o PHPMailer (inclusive el smtp de gmail).
Te ejemplos para PEAR:Mail y Phpmailer, ambos utilizando el smtp de gmail para enviar correos
Si vas a unas un smtp ssl como el de gmail, el servidor debes tener la libreria OpenSSL.
Saludos.