You have probably already had a look but I do not recall seeing it in any posts above.
There is a recover deleted emails option in outlook. I cant see exactly where atm as I dont have office installed. But you might be able to find them in there if the user deleted them.

However if he used the Shift+delete combination this deletes them properly and they do not appear in there.

All depends on the users skillbase if they are trying to sabotage your operations