It took a while to find this answer. To clear the Outlook 2010 contact search drop down (what used to be called the QuickMRU in earlier versions of Outlook) you have to go to this registry key.
HKEY_CURRENT_USER\Software\Microsoft\Windows NT\CurrentVersion\Windows Messaging Subsystem\Profiles\profile_name\0a0d020000000000c000000000000046\101f0446
You can edit it or delete it, but it is a binary type so it appears to store the information in Unicode.
I found the answer here.