probabilmente è il secondo esempio quello che dovresti utilizzare, questo infatti si connette al server SMTP del dominio in questione (ad esempio gmail.com) e inserisce l'indirizzo mail completo.
Come spiegano in quel post questo sistema funziona LA MAGGIOR PARTE DELLE VOLTE perchè solitamente il server risponde OK 250 se l'indirizzo esiste o errore se l'indirizzo non esiste.

Non è una prova assoluta al 100% (non ho approfondito quel post, mi sono fermato ai primi risultati, magari sotto ce ne sono altri migliori) ma è comunque un inizio!

EDIT: mail() non ti assicura se l'indirizzo esiste o meno