Если способ доступа был через браузер -- сушите веслы.
Если использовался POP3 (через Outlook, например), то есть смысл поковыряться в файле БД почтовой программы. Пару раз удавалось поднимать из .PST файлов аутглюка письма, удаленные пользователем через Shift-Del (т.е., мимо корзины).