Geh mal in PhpMyAdmin, und schau dir die Tabellenüberhänge an, sollten da große Werte stehen (über 1MB beim VMS) dann optimiere mal alle Tabellen.

Ansonsten: Gibt es Abfragen, die bei jedem Seitenaufruf durchgeführt werden (Ländercode o.ä.; meist: linkes_menue.php; header.php; rechtes_menue.php)?