Outlook search is unfortunately one of the big issues we have with grommunio (supported) as a hosting provider.
In online mode the search is very unreliable and the very first search attempt usually fails with an error, that Outlook tries to communicate with the server, which takes half a minute or so, then times out. A second search attempt does not show that error again and eventually finds something, maybe not. Every next search attempt may finds something, sometimes a few mails, but usually never all mails and it's quite slow (speed improved however over the past few months).
The funny observation, where the search result list first shows a list of mails found and in the end removes them from the search results, is known to us and we identified, that those preliminary results, are found inside the trash folder, which at the end of the search activity, get removed from the list. Removing those mails from the final search result does absolutely make sense, but it shouldn't show them to the user in the first place.
Unfortunately, cached mode does have it's own issues 🙁
While search results, once indexing is over, are quick and complete at the beginning, after a few weeks/months of usage, the search results are incomplete and the only way to solve the issue is temporarily change to online mode, delete the .OST file and reenable cache mode, which creates a new .OST file, which again needs to be indexed. Indexing takes ages on 10GB mailboxes...
So, all in all, Outlook search for us is still a big construction site. Oh an we did adjusted exmdb_search as well, which first seemed to help a bit, but in the end, not that much. The main issues remain since months...