Schau mal in folgendem Pfad nach und sichere als erstes alle dort befindlichen *.dbx Dateien (diese enthalten sämtliche Mails).
C:\Dokumente und Einstellungen\ USERNAME\ Lokale Einstellungen \Anwendungsdaten \Identities \{Identitätsnummer} \Microsoft \ Outlook Express
Hast du den Speicherpfad geändert, findest du diesen wie folgt:
Extras -> Optionen -> Wartung -> Speicherordner
Kontakte werden in Outlook Express gesondert im Adressbuch gespeichert. Der Pfad hierzu lässt sich über die Registry unter HKEY_CURRENT_USER\ Software\ Microsoft\ WAB\ WAB4\ Wab File Name herausfinden und lautet im Regelfall C:\Dokumente und Einstellungen\ USERNAME\ Anwendungsdaten \Microsoft \Address Book \USERNAME.wab
Sehr ungewöhnlich (insbesondere das Mails gelöscht werden)
Ich würde mal das ganze System auf Parasiten untersuchen, sofern du 100%ig ausschließen kannst, das du die Mails nicht ausversehen selbst gelöscht hast.