You can purchase software that claims to recover deleted files for you. This site offers a free trial of there software (although I've never tried it) along with some hints:

http://www.accuratesolution.net/solu...ok-express.htm

You can probably find free message retrieval software on downloads or tucows