People also try to look up the MX records for the domain to see if it has a valid mail server. This works 95% of the time--but breaks in certain cases leading to false positives.

As olavk said, just do basic validation (@ exists) and send off a confirmation e-mail. It works 100% of the time.