You should check with SMTP.
That means you have to connect to that email’s SMTP server.
After connecting to the SMTP server you should send these commands:
HELO somehostname.com
MAIL FROM: <no-reply@gmail.com>
RCPT TO: <emailtovalidate@domain.com>
If you get “<emailtovalidate@domain.com> Relay access denied” that means this email is Invalid.
There is a simple PHP class. You can use it:
http://www.phpclasses.org/package/6650-PHP-Check-if-an-e-mail-is-valid-using-SMTP.html