Servus Stefan,
das waren auch eher Möglichkeiten zur Fehleranalyse als fertige Lösungen 
Ich habe gerade mal eine Testbestellung gemacht - das geht natürlich garnicht, bei mir war es sogar länger als eine Minute.
Das positive, ich dir jetzt schonmal sagen das kein AJAX Aufruf im Hintergrund hängt.
Ich nehme an du hast nach dem oben von mir beschriebenen deaktivieren des Plugins den Cache aktualisiert und auch überprüft das es wirklich nicht mehr läuft? Ich meine das Logging ist ja eindeutig genug, die Schleife wird zu 99% bis zur maximalen Skriptlaufzeit ausgeführt. Kannst du mal bitte einen phpinfo anlegen und mir die URL per PM senden?
Auch wenn 128M nicht das Nonplusultra sind, würde ich das vom dem Fehler losgelöst als mittelfristige Optimierung betrachten (der Shop läuft insgesamt sehr langsam - zum Vergleich, gucke dir mal www.haustierkost.de an, eines unserer Kundenprojekte). Generell kann man sehr schwer eine pauschale Aussage dazu treffen ob 128M zuwenig sind(Es müssen immer die individuellen Aspekte betrachtet werden: z.B. Traffic, Anzahl der Transaktionen, Frontendcaching vorgeschaltet, Memcache aktiv usw.) Wir beraten dich natürlich ebenfalls gerne, setzen aber in Sachen Hosting immer auf skalierbare Lösungen wie AWS oder Domainfactory Jiffybox.