Ich kann mir nur ein lokales Problem vorstellen. Du schreibst ja, dass ihr 800 Artikel habt? Das ist ja noch „wenig“ und ich habe von dem Problem noch nie gehört!
Hast du alle Methoden zum Cacheaufbau probiert? Privat habe ich ein kleines „normales“ Shophosting Paket mit ca. 3000 Artikeln und baue den Suchcache schon immer innerhalb Sekunden „live“ auf.
Hast du ggf. eine sehr individuelle Konfiguration der Suche? Werden sehr viele Felder zusätzlich durchsucht? Kommen Ergebnisse schon ab einem Zeichen? Irgendwas muss ja stark vom Standard abweichen.
Was sagt dein Hoster? Ist da evtl. wirklich was enorm eingeschränkt?