Here's a couple of solutions:
- Permanently delete your deleted items. This is based on the theory that once you have deleted a mail item, you should NEVER HAVE TO LOOK AT IT AGAIN. This is a good theory, but unfortunately we don't always follow it in practice and there's no recovery
- Move the items into subfolders under Deleted Items. This is a good solution as you can manually archive items, making it easier to search. You can permanently delete items when they reach a certain age.

Figure: Good Example - Deleted Items ordered into time periods
NOTE: A hot tip for making it easy to search for an accidentally deleted item is to add the "Modified" field into your Deleted Items view and sort by "Modified". The item from two months ago which you just accidentally deleted will be sitting at the top.

Figure: Sort by "Modified"
We have a program called SSW LookOut! for Outlook to check for this rule. It leaves a reminder in your Inbox to remind you to clear your deleted items folder