to avoid this in the future on the class of service/messages page there is an option to send messages to deleted items folder.the user must be of this calass of service type. Then you can bump up your deleted items retention time on exchange . this is done by right clicking on mailbox store under your server and selecting properties/limits. bump this up to 30 days if you choose. as the name indicates this will keep items in the delted items folder for the time specified and/or until a backup occurs
for the messages that are already gone they are gone unless you can restore them from backup because I am sure you are doing that. If you have an exchange aware backup solution capable of doing brick level backups then you can restore down to the individual piece of mail. If you dont you can use exmerge (not for the items already gone but to restore in the future) which will backup individual mailboxes to a .pst file and then you can restore from within outlook.
http://forums.cisco.com/eforum/servlet/NetProf?page=netprof&CommCmd=MB%3Fcmd%3Dpass_through%26location%3Doutline%40%5E1%40%40.ee8efe2/0#selected_message
