Aus Erfahrung kann ich guten Gewissens sagen, ja, es ist möglich seinen Prestashop mit mehreren tausenden Artikeln und Kategorien unter einer halben Sekunde laden zu lassen.
In meinen letzten Projekten bin ich von Apache zu Nginx Servern gewechselt, welche mit dem PS Cache, PHP Memcache und diversen anderen Features (vor allem Google Pagespeed) sogar die größten Prestashop-Instanzen zum Schnellläufer hat werden lassen.
Fazit vom Entwickler: Ja, es ist möglich, wenn man die richtige Hard- und Software beim Hoster hat.