Suppongo che si limiti a provare ad inviare una mail collegandosi all'SMTP del destinatario: se il server SMTP dice che la casella non esiste (cosa che diversi server SMTP fanno appena viene trasmesso l'indirizzo del destinatario) ha la (quasi) certezza che, appunto, non esista. D'altra parte se non erro alcuni server SMTP aspettano fino alla fine del messaggio prima di dare l'errore (e in tal caso il servizio in questione non credo che possa fare nulla, dato che annullerà sicuramente la sessione prima).
Ma soprattutto, in genere il comportamento in caso di destinatario sconosciuto è configurabile: invece di fornire un errore, come detto da denis76, è possibile configurare il server SMTP per fare finta di prendere in carico il messaggio e poi effettivamente buttarlo via, oppure girare tutti gli indirizzi sconosciuti al postmaster, o altre cose ancora (vedi immagine allegata).
In sintesi, non c'è modo completamente sicuro per sapere se un indirizzo esiste o meno.