I've found that the best ways for validating email addresses, in order, are: checking for the '@' sign, resolving the hostname to the right of the '@' sign to see if it has MX records (or an A record, since the specification technically also allows sending mail to the server at the A record), and sending an email to the address that includes a verification link that the user must click.

The first two can be done without requiring any additional work for the user, but people are so used to clicking verification links that they don't really mind that either.