I went to one of the computers that had cache mode disabled since this issue happened and I was able to search on it with no issues after enabling it the first time. Hope that info helps.

Have you considered rolling back just one computer as a test to make sure you are dealing with the same bug we are talking about here? May be worth a shot.

Unfortunately, we have 1000+ users and rolling back an update on every machine or disabling and re-enabling cache mode (which we have turned on via GPO) are not feasible options.

@ryandempsey We have on premis exchange 2016, when I heard it was working I tested mine but it failed on first try. So, I disabled Exchange cache, open Outlook, test search, close outlook, enable cache again, open outlook and search worked as it should.

@ryandempsey Try rolling one of the problem computers back to at least the build I had listed, start outlook, wait 30 seconds, close it, open it again and see if search works. If it does, you have the same issue the rest of us do, if it is still broken, its probably something else.