It depends on your system but yes, quite often, "deleted" messages can sometimes still be found in personal folders, archive (*.pst) files or in the Exchange database itself. The question is how much time you have to invest in the project. If it'soutside e-mail, chances are that a copy also resides somewhere on the Internet. And again, the question is how much is it worth to recover it? For a sexual harassment or industrial espionage case, it might be worth it. For your garden-variety e-mail violator who occasionally uses his/her company account to send a Happy Birthday note to a relative, it's pretty hard to make a business case for prosecuting the violation.
The better answer is to implement logging or Message Tracking and let your users know exactly what you're doing. That way, you have evidence of the message before they ever get it. It tends to bring e-mail mischief to a rapid halt and doesn't waste your time looking for a needle in a haystack.
paul