The solution is to stop trying so hard. As you said, the problem is fuzzy, so you do... a fuzzy search, return a bunch of results, and let the user pick. If th

The solution is to stop trying so hard. As you said, the problem is fuzzy, so you do... a fuzzy search, return a bunch of results, and let the user pick. If the dataset is too large, then you just let the search include more details. "Mueller from Berlin" or "Muller born on july 7th" are much better queries to find a specific person than a perfectly written "Müller". In fact, if you were to crack the problem of searching by considering all applicable rules, the system would still be useless because people make mistakes all the time and the Müller guy actually wrote "Miller" while signing up ;P