You may have wondered “How do I remove my company directory search history entries?”  Well , here’s a nifty trick you can do:

1. From the file explorer, navigate to Application Data\Microsoft\Outlook\
2. Delete “GalSeachHistory.dat”

This will clear your search entries from the company directory.

Note: Clearing search history in this way isn't a supported scenario, but it should work in Windows Mobile 6.