Well, if you deleted them within 30 days, and you do not have your Exchange setup to purge deleted mailboxes immediately then there’s still hope for you! In fact, you may have mailbox purging setup to occur after backups only in which case your mailbox may be available more than 30 days even.
The quickest, easiest way to get access again is to create a user in Active Directory without an associated Exchange mailbox. Then, open up Exchange System Manager (ESM) and navigate to the mailbox you deleted (it’ll have a red X on it). Right-click and select Reconnect. Enter the new user’s id and click OK and it should associate that mailbox with that new user. Upon logging into a computer and setting up Outlook, you’ll have access to the contents of that mailbox again.
Software: Microsoft Exchange Server 2003