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: <[email protected]>
RCPT TO: <[email protected]>
If you get "<[email protected]> 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