This answer assumes that user email is saved in the Exchange mailbox, and not individual .pst files.
1. The deleeted items retention time must be set (the default is 0 days) on the mailbox store.
2. If this setting has been set to other than 0(and the retention time limit hasn't expired), the user need only go to the Tools menu in Outlook, choose "Recover Deleted Items", select the item(s) to recover, and click Recover Selected Items. The recovered item(s) will appear in the user's Deleted Items folder.
3. If the deleted item retention limit has expired or is set to 0, your only option would be to attempt to restore from backup.
Good luck.