I almost dare not suggest it, but what about the Text::Soundex module? Or the more modern variant Text::Metaphone?

By itself it will not be useful as it will hash into a too small space, but as an additional criterium it is to be considered, I feel. It would not account for casual mis-typings of course, but would assist with variants of the name, typed by someone who played it "by ear".

Wikipedia has some interesting links to more sophisticated algorithms.