One nice looking trick I've seen is checking the domain of the email address for an MX record. (e.g. http://php.dzone.com/news/php-email-validator-email-mx-d)
Possibly this approach is too slow to use by itself without a regex. Also maybe there are other problems with this method I'm not aware of?