I ran into this issue when migrating users to Exchange Online, while running Outlook 2016 MSI 32 bit.
Once a user is on Exchange Online, Outlook starts leveraging the power of FAST search. This search occurs on the Exchange Online end, rather than the device end, and is designed to give quicker results while being more reliable than Windows Desktop Search. There’s a great write-up on this on Microsoft’s TechCommunity that goes into much more detail.
It does depend what sort of search you do as to whether it’ll use FAST or Windows Desktop Search too, but the most basic of searches will use FAST. There’s also timeouts and speed checks that can force it to fail back to Windows Desktop Search.
However, there are some catches with this search from my testing. If you do an email search and decide to delete one of the emails in the results, it appears that nothing has happened. You can delete and delete, right click, press the delete key, click the X to delete and it all appears to do the same – nothing. In the background though, it has actually deleted your email, it just doesn’t display this in any way. It’s like the search results are a static result and won’t update on an action like this.
This behavior can be confusing for a user, especially when they’re used to seeing emails disappear and react when something’s done to them.
There’s another catch that depending on your environment, might be more of a deal breaker. If you use the category field, flag, or extra fields, for example when filing a document into a DMS system, those aren’t displayed or updated in a FAST search. If your users need this to effectively manage their emails, then it’s worth looking at just disabling FAST search via Outlook altogether.
As mentioned in the above post and this Technet article, there’s a single registry setting that can disable FAST search:
Value name: DisableServerAssistedSearch
Value type: REG_DWORD
A restart of Outlook is needed after this change, and users won’t be alerted of anything different. Search will just start using Windows Desktop Search (which was always running anyway) and not know any better.