Avevo pensato anche io per prima cosa alla soluzione di webpos, se ti sembra troppo laboriosa/complicata potresti provare questa classe:

http://www.phpclasses.org/browse/package/1519.html

Pare che contatti l'smtp per controllare se l'indirizzo esiste. (io non l'ho mai usata)

Ciao