Hallo,
es gibt noch eine weitere Möglichkeit, weshalb du die gelöschte Nachricht nicht findest.
Bis OL2007 wurde für alle POP3-Konten als Datendatei die Outlook.pst genutzt, alle POP3-Konten hatten somit auch einen gemeinsamen Papierkorb.
In OL2010 wird für jedes weitere POP3-Konto eine eigene Datendatei für den Posteingang verwendet. Du solltest mal links in der Kontenübersicht das entsprechende Konto 'aufklappen' und in dessen Papierkorb nachsehen.
Gruß
Kalle