How can I verify a user is authentic?

I've recently installed a plugin called "Stop Spammer Registrations" found here:

http://wordpress.org/extend/plugins/stop-spammer-registrations-plugin/

It has an option to redirect a user to a page if they've been identified as a spammer. I would like to offer anyone that lands on that page one last chance at redemption if the can provide sufficient evidence they are not a spammer. I can create a Gravity Form and collect some info, but I'm not sure what to ask for. I was thinking of things that would prove they are real like links to their facebook page, linkedin, gravatar, etc.

Should I even bother?

Thanks!