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.