We tried to implement the email existence check the next way:
0. E.g. we have the email user@example.com
1. Find the mail server by MX-record for the example.com. Let it be mx1.example.com.
2. Connect to the mx1.example.com:25 via the socket.
3. After all necessary greetings, send the VRFY request giving the username user. The server must confirm whether this email really exists.
4. In real life most servers just respond OK.
Other way is to try to get the error on the wrong RCPT value. But most servers, again, just accept any wrong username, returning the OK.
This was tested on gmail.com, mail.ru and other public mail hosts: thy just ignore the RFC.
Carpe diem