You can read more about this issue over at Ron Grzywacz’s blog.
Now over to the topic of the post. Once fuzzy name search is working, be careful of restarting the search host controllers on your query servers. The reason is that the fuzzifying logic lives in the query component, and once the component is restarted it will have to rebuild the name cache.
And, rebuilding the name cache can take up to 24+ hours before it’s complete in a living environment with 17,000+ people in it. Which means name search performs suboptimal every time the search host controller is restarted or the query component is restarted. This will also impact the dictionary used for the people result block which is enabled by default in a search center.
Also remember to have the right query language for fuzzy/phonetic name search to work in the first place.
Thanks to Pamela Joslyn for all the troubleshooting and heavy lifting around this issue :)