APC installeren zonder deze te activeren in Magento is zinloos.
Cache installeren op disk is vrij zinloos (gebruik tmpfs in geheugen, kan niet op shared hosting)
Magento optimaliseren zonder bij MySQL te beginnen is zinloos.
GZip aanzetten zinder naar mod_expires te kijken is zinloos.
Cache aanzetten op een webshop zonder bezoekers geeft geen reeel beeld.
Heb je voor een 'Flat catalog' gekozen in de configuratie?
Zoals je leest, genoeg zaken om aan te pakken maar enkel het samenspel tussen alle factoren zal je helpen.