Frank, nachdem das Kind nun schon bei web.de in den Brunnen gefallen ist, hoffe ich nur, das du dich schnell von diesem Anbieter löst.
Alternativen wurden hier ja bereits genannt.
Grundsätzlich möchte ich dir aber empfehlen immer selbst ein Backup vorzuhalten. Nur dann kannst du sicher sein, das du wieder an deine Daten kommst. Auch wenn das eigentlich für einen Anbieter, der für seine Leistung GELD verlangt selbstverständlich sein sollte.
Bei günstigen Anbietern von E-Mail-Konten kenne ich eigentlich nur tuffmail.com und fastmail.fm die auch explizit mit Backups werben. Bei fastmail.fm kann man E-Mails bis zu einer Woche nach Löschung "zurückholen". Evtl. Nachteil dieser Anbieter: Alles in Englisch.
Die vorgeschlagenen deutschen Anbieter DomainFactory und HostEurope bieten kein E-Mail-Backup an - jedenfalls nicht gegen "versehentliches" Löschen.
Neben den bisherigen Erklärungsversuchen (E-Mailprogramm, Einruch) hätte ich noch einen anzubieten: Da das Account deinen Aussagen nach nur sehr selten genutzt wird, wäre es auch möglich das die tolle "Datenschutzfunktion" der UI-Gruppe (web.de gmx.de etc.) zugeschlagen hat - loggt man sich für längere Zeit nicht ein, löscht der Anbieter kurzerhand alle Mails (zum Zwecke des Datenschutzes [sic!]) beim nächsten Login.
Für welchen Anbieter du dich auch entscheidest, so möchte ich dir doch ans Herz legen, die E-Mails lokal zu speichern und in deine bestehende Backup-Strategie einzubinden.
Für die lokale Kopie gibt es viele Möglichkeiten, z.b. ein einfaches E-Mail-Programm, was die E-Mails einfach nur holt, ohne sie auf dem Server zu löschen, über "Bastellösungen" wie getmail/fetchmail, zu "professionellen" Programmen wie z.b. MailStore Home. Persönlich nutze ich das Programm IMAPSize, dessen genuztes Protokoll IMAP wird aber von vielen Free- und Billig-Anbietern nicht unterstützt.
Gruß, Tim