Puedes hacer dos cosas:
1) (lo primero) .. Mirar que la sintax del e-mail sea correcta. Más info en esta FAQ del foro PHP:
http://www.forosdelweb.com/showthrea...423#post333423
2) (opcinal) .. Mirar si existe físicamente ese servidor @tal.tal y ese usuario en el usuario@ ... Para eso hay que hacer una conexión por sockets al servidor SMTP en cuestión y esperar respuesta. Si bien es un proceso "seguro" como que la cuenta existe es lento en ejecución y puede fallar en ese instante .. lo cual no implicaría que no exista . simplemente que falló la conexión .. así que repetir la conexión una y otra vez hasta que responda es lo que se haría "leeento" ..
Un saludo,