MX record is not required. You should allow hosts with only A records too.
practically speaking, most respectable email services will have an MX record. i tested it on about 30,000 emails & a simple MX lookup caught about 40 gmial's and only 1 false positive.
Re:Perfect email regex finally found
by drivebyacct on Friday May 28, 2010 @04:22PM
(#1387532)
I suggested that a while back but was told that due to spam, you can get lots of false negatives from this technique and others.
The best way to validate an email remains to be a test email apparently.
You must be thinking of something like this: http://www.webdigi.co.uk/blog/2009/how-to-check-if-an-email-...
Merely looking up MX records is something you do for a _domain_ and it's no different than the DNS requests your computer makes when you go to a website.
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?