Der Provider muss eigentlich ein Backup von seinem Mailserver haben. Du müsstest ihn "nur" dazu bringen, das wieder einzuspielen...
Ich denke, als "dummer, kein Geld bringender" Privatkunde bist du denen ziemlich wurst und die pfeifen dir was, selbst wenn sie ein Backup hätten (was ich eigentlich bezweifle).

Was gefährlich ist: Viele POP3 Mailprogramme sind per default so eingestellt, daß die Mail nach dem Abruf vom Server gelöscht werden, Outlook Express imho auch (habs allerdings seit Jahren nicht benutzt). Hast du vielleicht mit sowas herumexperimentiert ?

Ich kann mich an die Vorredner nur anschließen: Mach regelmäßige Backups deiner Mailbox (mit einem POP3/IMAP fähigen Client). Der Unterschied zwischen POP3 und IMAP: Während du bei POP3 nicht wirklich weißt, welche Mails du abrufst, bekommst du bei IMAP die Möglichkeit, dir die Kopzeile anzusehen und auszuwählen, was du runterlädtst. War vor allem bei Einwähl-Verbindungen durchaus interessant, mit DSL sollte die Zeitersparnis gering sein.

Wichtige Daten vertraust du besser niemandem an, schon gar nicht eim Provider.

Ich weiß, das wird dir für dein aktuelles Problem nicht mehr viel nützen, aber vielleicht hilft es in Zukunft, solche Ereignisse zu vermeiden....