“Well I would hope you have backups of the database he was on. You will need to do a restore of that database, Once you have performed that step you can exmerge his mailbox out to a PST and then he can import that pst into his current mailbox. The steps to perform the restore depends on the backup software you are using. If you need assistance with that part let us know. Thanks!”
When you delete a user there mailbox stays there for 30 days, if you recreated the same user name you should be able to go into System manager and re-link the mailbox.