Leistung bei 70.000 Artikeln

Hallo Zusammen!

Ich habe mit oxid ce einen Shop mit dem kompletten Sortiment unseres Großhändlers installiert. Über Import- und Update-Skripte läuft dieser auch (mehr oder weniger) Pflegeleicht. Nur das wirklich ein Performance Problem vorliegt. Unser derzeitiges Hosting-Paket sieht folgendermaßen aus: uns stehen 20 Sek. CPU Zeit, 90 Sek. Scriptzeit zu und wir sind mit 20 Kunden auf einem CPU-Kern.
Leider passiert es zu oft, das die Zeit nicht ausreicht, um z.B. Suchanfragen durchzuführen und man eine leere Seite zurückgeliefert bekommt.
Verschiedene MySQL-Befehle wie ANALYZE TABLE und OPTIMIZE TABLE haben nur eine marginale Verbesserung gebracht.

Nun meine Frage ob jemand schon Erfahrung mit oxid und solchen Shop-Dimensionen hat? Welche Serverleistung habt ihr gekauft, damit der Shop in annehbarer Geschwindigkeit läuft?
Vielleicht hat jemand Vorschläge, was man noch an der DB ändern/optimieren kann.

Gruß
StockInsAug

Als Ergänzung: Der normale Aufruf auf dem Live-Server dauert ca. 8-9 Sekunden. Lokal ist der Shop, mit der gleichen DB auf einer virtuellen Debian-Maschine, mit 2GB RAM, 1 CPU-Kern mit 3GHz installiert. Lokal dauert der Aufruf ca. 4-5 Sekunden.

Bei einem solchen Shop sollte man auf keinen Fall auf einen Shared Server zurückgreifen. Sieht man ja das das nicht funktioniert. Unser aktueller Server entspricht in etwa dem Managed Server Business bei Profihost.