Ich denke das Problem ist nicht das Cookie, sondern die Session-Daten, die auf dem Server (im Temp-Verzeichnis) abgelegt werden. Das Session-Cookie enthält ja kaum mehr als die Session-ID. In der Session-Datei werden dann sämtliche Session-Daten abgelegt - und das können unter Umständen recht viele werden.
Ich vermute mal, es werden zuviele Daten in der Session abgelegt - wie und warum, kannst nur du wissen (oder halt bei Strato anfragen). Ist das ein Cookie, was von WP gesetzt wird? Hast du vielleicht Plugins aktiviert, die viele Daten sammeln und in einer Session ablegen? (Warenkorb eines Shop-Plugins z.B.)