[papaf]

Another option is checking server side using whatever is your language equivalent of: http://search.cpan.org/~rjbs/Email-Valid-0.188/lib/Email/Val...

This checks email addresses using regexps and DNS.

[ceejayoz]

I'd imagine domain squatters have snapped up all the common misspellings of popular mail providers, so a DNS lookup probably isn't as beneficial as you might imagine.