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.
As someone who owns {commonFirstName}{commonLastName}@gmail.com, I _hate_ services that don't require you to validate the e-mail address you sign up with. And there's a special place in hell reserved for people who write services which don't validate the e-mail you sign up with, but do require you to sign in with your credentials in order to unsubscribe.
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.