One thing I have done in a situation like this was to create an artificial hash of the user info. It ended up giving me a 95% hit rate. Something like :

Hash = SoundexOfLastName + SoundexOfStreetName + First3OfZipCode

So Jim Johnson at 123 Fair Oaks Ave in 12345 would hash to:

"J525F620123"

So just let them enter their user data, hash it, and see if you have any hits against that hash column in your data base.

Pretty hard to hack, but pretty easy to hit, even with misspellings, etc., and not a lot of suffering by the user.