Instead of verification, you could use the emailaddress as a login-method. Don't use passwords, but let the users login by email, sending a mail with a time-limited authentication-token and make them login that way. That way you don't have to deal with passwords, and you will know the user has a mailbox which they control.
I’ve thought about this method. I think this is what should be done for sites where you log in very infrequent (say, yearly). Do you know of any examples where this is implemented?
About the frequency: there aren't many situations where a user has access to your application, but not to email. I've been thinking about that, but when you have access to a browser, (most of the times) you have access to your mail.