… dass exakt die erste Suchanfrage nach 0:00Uhr extrem lange dauert (ca.15 Sekunden bei 1654 zu durchsuchenden Dateien).

Merkwürdig. Und vermutlich ist die Ursache nicht leicht zu lokalisieren.

Handelt es sich wirklich um die erste Anfrage an den Server? Oder die erste Anfrage von einem bestimmten Client.
Bei der Klärung dieser Frage könnte evtl. ein Blick in die Serverlogs helfen. Suchanfragen sind dort z.B. am Aufruf der Datei throbber3.gif zu erkennen.

Taucht das Problem nur innerhalb einer begrenzten Zeitspanne nach Mitternacht auf? Laufen während dieser Zeit resourcenfressende Prozesse auf dem Server?

Vielleicht hat auch der Serveradmin eine Erklärung / Lösung.

Noch eine Idee: Was passiert, wenn die erste Suchanfrage im Mobilfunknetz gestellt wird?

Ich hoffe, dass es sich nicht um einen Fall wie den hier geschilderten handelt, wo letzlich erst ein Wechsel des Providers die Lösung brachte.