I've used the Instant Search feature and it seems to remember my previous 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
<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