I’ve used the Instant Search feature and it seems to remember my search queries.
Is there any way I can delete this cache or remove items from it?
Outlook stores your recent searches in the registry in the following key;
HKEY_CURRENT_USER\Software\Microsoft\Windows NT\CurrentVersion\Windows Messaging Subsystem\Profiles\<profile name>\0a0d020000000000c000000000000046 Value name: 101f0445
Replace <profile name> with the name of your mail profile. Often this is simply called “Outlook” unless you have specified otherwise.
Delete the Value name “101f0445” when Outlook is closed to empty the search cache.
Note 1: If you are not comfortable editing the registry yourself you can use OutlookTools (free) instead.
Note 2: In order to clear other cached lists see the guide: Clear the Most Recently Used lists