Und soeben habe ich durch Zufall die Ursache herausgefunden

Die Suche kommt sich mit der Seitenzählung in die Quere, die nach dem Öffnen des Dokuments stattfindet. Bei hunderten Seiten dauert sie eine Weile - und erst wenn sie abgeschlossen ist (also die Seiten durchgezählt sind), dann startet die Suche so richtig (sie läuft schon zuvor, aber eben sehr verzögert).
Könnte man das vielleicht technisch so ändern, dass diese beiden Prozesse unabhängig voneinander laufen? In Microsoft Word scheint das der Fall zu sein, denn da dauert zwar die Seitenzählung auch ihre Zeit, aber unterdessen lässt sich die Suchfunktion bereits ungehindert benützen.