Simon -
That is indeed a tough requirement to fulfill.
If you're doing name lookup and you're dealing with primarily English names, the various soundex algorithms are quite useful for locating names that "sound" alike but are spelled differently (e.g. Smith and Smyth). The soundex algorithm generally reduces each name to a small string (4-6 characters). Using this code as a key, one can then retrieve all records with names similar to the one being searched for.
We developed a hospital patient search facility using this technique (with modifications for un-named babies, e.g. Baby Smith, sex, first initial, and birthdate/age). We've been using it quite successfully for many years to search a growing database of about 1,000,000 names.
Regards.
Glenn