Since our exchange server mailbox database (EXCH 2010) /SBS2011) was corrupted and repaired (with lingering issues like "Fail to sync with Smartphones"), users are complaining that Search in OUTLOOK 2010 quits working. Whenever that happens, I check "Microsoft Exchange Search Indexer" in Services.msc on SBS2011, it shows "Started". But I have to restart this service to get the Search working again in OUTLOOK for several days. And then it quits working after several days.
Is there a permanent solution to this?