Vielleicht einfach mal das Konzept überdenken? Oder den Anwendern erklären, dass sie entweder 20-30 Sekunden warten müssen, wenn sie die gewohnte Bedienung nicht ändern wollen?
Du steckst jetzt viel Zeit in deine ganzen Überlegungen und Klimmzüge. Manchmal muss man dem Anwender auch mal zumuten, dass sich was ändert.

Ich hatte vor Jahren etwas ähnliches.
Mit den Datenmengen war die Bedienung nicht akzeptabel. Also habe ich das Lookup nachgebildet, aber etwas umgesetzt, was du auch schon angedeutet hast. Erst ab einer gewissen Anzahl an Buchstaben werden überhaupt Daten geholt. Zusätzlich habe ich die Pausen zwischen den Tastenanschlägen geprüft und erst, wenn offensichtlich nichts mehr getippt wird, die DB-Abfrage angestoßen. Die Kombination dieser beiden Dinge hat sehr gut funktioniert. Bei mir waren es mindestens 3 Zeichen und die Pause größer als 300 Millisekunden, wenn ich mich richtig erinnere.
Also einfach mal dein Standard-Lookup rausschmeißen und was eigenes programmieren. Was ich damals gebastelt hatte, war nicht wirklich kompliziert. Außerdem spart man sich auf diese Weise auch noch die Hintergrundprüfung, ob die Daten aktualisiert werden müssen. Der lokale Rechner und das Netzwerk werden vermutlich auch nicht mehr so stark belastet. Das hängt natürlich auch von den Daten ab, die dort vorliegen.

P.S.:
Ich gehe mal davon aus, dass du eine vernünftige Indexierung auf den Such- und Sortierfeldern hast.