Moin,
zunächst bitte die genaue Exchange-Version ermitteln und posten:
http://blog-schulenburg.de/index.php/kategorie-als-blog/87-exchange-build-nummern
Es gab mit einem CU mal ein Problem, das musste man die Suche am Server neu indizieren - sollte aber inzwischen behoben sein.
OL 2010 mit Exchange 2016 läuft zwar, ist aber kein idealer Client - wollt / könnt ihr zeitnah auf Office 2016 Pro gehen?