How-To: Clear Company Directory History
 

As found here, below is how you clear out the search history from the company directory (Exchange) side of Outlook Mobile

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