Wir konnten das Problem lösen - die Cookies waren unschuldig. 
Anhand des Zeitpunkts, ab dem wir keine Bestellungen mehr gefunden haben, wurde uns irgendwann klar, dass es sich um die Zeitumstellung handeln muss.
Und genau so war es auch:
Der Server war in der Winterzeit, in der Config von MariaDB/mySQL aber noch Sommerzeit eingestellt.
Sobald wir das angepasst haben, zack! Geht wieder.
Ich weiß nicht ob das als Bug klassifiziert werden kann oder ein klassischer Anwendungsfehler von uns, aber tatsächlich ziemlich merkwürdiges Verhalten von Shopware.