Check out a post from Petri here.
Scroll about halfway down and look for “How do I recover hard-deleted items via Outlook?”
Try that, sorry I don’t have anymore info for you at this time.
When you create a new mail store it sets a default retention of 7 days, so unless you went in and removed that you should have a 7 day retention of your deleted items. If you do not then nothing short of a restore will bring the deleted mail back provided the mail store was backed up after the mail was received and before it was deleted. You ARE backing up the mail stores right?