Ich konnte das Problem erfolgreich selbst lösen!
Falls das hier mal jemand liest, der das gleiche Problem hat und auch Strato nutzt: Bei Strato selbst kann man in den Email-Postfächern eine Mail-Wiederherstellung starten. Etwas missverständlich steht da, dass diese Wiederherstellung sich auf die letzten 30 Tage bezieht. Vielleicht hat man danach ein paar mehr Mails in seinem Postfach, als man es vorher hatte, aber: Alle meine Mails sind wieder da!