Habe es in gemeinsamer Arbeit mit dem Admin zum Glück hinbekommen. Und zwar hat Microsoft wohl irgendwie selbstständig alle E-Mails gelöscht - er hatte nämlich nichts dergleichen konfiguriert.
Die Wiederherstellung kann man sogar selbst vornehmen: Und zwar geht man in Outlook oder im OWA auf Gelöschte Elemente und dort auf "Zuletzt aus diesem Ordner entfernte Elemente wiederherstellen" bzw. "Gelöschte Elemente wiederherstellen". Damit kann man alle von Microsoft entfernten E-Mails zurückholen. Bei mir fand das große Löschen wohl am 16.4. zwischen 2:12 und 2:29 statt.
Die Accounts sind bis Ende Mai einschließlich aktiv - eine Weiterleitung habe ich mir bereits eingerichtet und wegen einer möglichen Übernahme der Domain sprechen wir auch noch einmal.