One of the mind boggling things about Microsoft Outlook is that even with zillions of settings in the preferences, you still can't easily clear private data like MRU lists by using an option in the UI. For instance, if you are using Outlook 2007 there's the Instant search box on every folder. If you click the drop-down and then select Recent Searches, you'll see a list of your most recent searches.... but there's no way to clear it! This is where the brilliant application OutlookTools comes into the picture. It's a sort of TweakUI for Outlook, and allows you to configure a ton of settings very easily, including the ability to let you clear the MRU lists.

You'll notice that there are a lot of options you can choose from. Make sure you have the correct profile selected in the drop-down list, and then click the buttons to clear. Odd that there's no Clear All button, isn't it? You can also clear the auto-complete email address cache using a different method. Download OutlookTools from HowTo-Outlook