Please allow searches to be specified using "regular expressions".
This is where the user specifies a pattern to look for rather than a fixed strings. This means that the user doesn't have to keep submitting searches for the same thing.
For example.
I'm looking for Henry Boot.
The problem is that "o" can look like o,a,s,0,c. "y" can look like y and v. etc (I'll keep it simple..)
Searching for him could result is searches for:
Henry Boot
Henry Boat
Henry Bost
Henry Boct
Henry Baat
Henry Baat
etc etc. Lots of separate searches.

However, a rexex search to achieve the above can be expressed as:
Henr[yv] B[oas0c][oas0c]t
(The square brackets are listing a choice of valid letters)

I realise that a vast number of users will struggle to use this, however it may be possible to have a user friendly regex constructor, or even have your own equivalence classes where "a" always matches the letters [oas0c].

Please consider this as a serious suggestion. It has the potential to improve people hit rates.