I think you're trying to make things too difficult. I've done something similiar on some sites I've designed - I'm simplifying it greatly for the sake of brevity.

Simply - when you have the person sign up - assign a random value to their database entry.
Have this value be a simple random number, say "58390".

Then mail them the url to an "activation" script. Something like http://yoursite.com/activate.pl?username=bob&code=58390

Then have the activate.pl script parse the variables and cross reference that random number (using the username) with the one that was assigned.
If that number matches the correct one for user "bob" then go ahead and make his account active because you know you have a valid email now.

You now know that this user has a valid email - without forcing them to type crazy random passwords. Only one click.
Hope this helps. You can get fancier, but this basic concept has worked for me.