After a windows 10 update 10.0.14393 Outlook 2010 won't search anymore.  one computer is stuck saying indexing incomplete.  Another showed completing indexing but still doesn't search properly consistently.  There are a dozen computers in this organization that just did the updates automatically and searches stopped; so this is not just one computer.  Ofcourse it's urgent too.  As a temporarily solution we are doing a system restore, but ultimately the update will install again.  There seems to be a bug with this update and we need a solution.

Searches for emails we know exist sometimes highlight but show other irrelevant emails.  Some don't show anything and one search seemed to work as expected. Is there another solution besides system restore?  Do we have to wait for Microsoft to address this issue?

show or hide updates:  http://download.microsoft.com/download/f/2/2/f22d5fdb-59cd-4275-8c95-1be17bf70b21/wushowhide.diagcab

Uhm...don't use crap like Windows 10?  Use 7 or 8.1.

I just figured out the solution myself. Sorry xpclient but it turns out there were a couple Windows 7 clients with the same issue. The problem was Outlook 2010 update KB3203467.  I tried many fixes before I found I had to do the following fix and must be done in this order as it doesn't work otherwise.  It's important to stop it from reinstalling this update once it's removed.

1. Open Advanced Windows update settings (Details depend on what version of Windows you have).  Uncheck "Give me updates for other Microsoft products when I update Windows".
   Also in Advanced update settings if it shows another option checked for "give me recommended updates the same way I receive important updates", uncheck that too.
   We basically just want critical/important updates only.
2. Uninstall KB3203467 update
3. Reboot
4. Go to Indexing options in the Control panel and Rebuild the Index.
5. Once Index rebuilt, go to Outlook and try a search, it may also show it is incomplete indexing but the numbers should start counting down for remaining items to be indexed.  Once the number hits "0 items remaining to be reindexed" your searches should work properly now.

I've done this successfully on 3 computers so far and 7 more to go.

Firing all the dedicated testers seems to be really working well at Microsoft.