Erst mal Danke für die Tipps.

agrep fällt leider weg, da auf dem Server kein Shellzugriff auf agrep möglich ist.

Mal sehen, was mir die 2.7 von String:Approx (als Perl-Only) an Langsamkeit bringt.

Ich sehe mir das mal an und schreibe ein Stresstest.