I didn't change the registration, but I'm actually using a more hands on security model. The "Community-Authenticated" role doesn't have any more rights than the "Community-Everyone" Role. I added a mod that sends an e-mail to all the members of the "Community-Administrators" role when there is a new registration. Then one of the Admin review the new registration, and if it's cool, adds the user to the "Community-Verified Members" role.
This is primarily being used for a small site for my church, and we're trying to limit the number of duplicate registrations because we're doing a default load of existing church members into the User's table.
I know somebody has written a mod that does just what you're talking about, where a random verification id is sent to the user before their membership is activated. Search here or the CSK sections to find it.
For my usage, I'm not so concerned that a person has entered a valid e-mail as verifying that the person should have access to the site in the first place.