Warum sollte Levenshtein nicht gut sein für die deutsche Sprache? Das Verfahren ist doch komplett unabhängig von der Sprache, und zählt einfach die minmale Anzahl von Ersetzungen/Einfügen/Entfernen-Operationen auf Zeichenebene. Ob ich da deutsche oder englische Wörter oder ein Stück DNA-Code reinschmeiße, ist völlig egal.
Wenn man also ähnliche Strings finden möchte, ist das unabhängig von der Sprache gut geeignet. Für
ähnlich klingende Worte (Meier, Mayer etc.) dann tatsächlich nicht unbedingt, und dafür sind dann sprachabhängige Algorithmen sinnvoll. Die Frage ist dann aber, inwiefern diese lautbasierten Verfahren Buchstabendreher erkennen können, oder wie diese mit anderen Zeichen (Klammern, Satzzeichen, ...) umgehen. Kommt halt auf den Anwendungsfall an.
Für die Titelsuche in meinem mp3-Player fahre ich mit Levenshtein (das ist ja in meinen oben verlinkten ApproxStrUtils implementiert) ganz gut - und da habe ich ja auch Fälle wie "Pink" und "P!nk" und ähnliche Scherze.
Edit: @TigerLilly: danke für den Link. Die Ergänzung mit "Verdreher als eine Operation zählen" muss ich mir mal genauer anschauen. Das scheint mir eine sinnvolle Ergänzung zu sein.