If you're getting a "Search complete. Showing only local results." warning from Outlook, then you must rebuild your Outlook search index. These are instructions for Outlook 2016, which works with Microsoft 365 versions as of, at least, early 2023.
This error may be caused by the Windows update process, among other issues. It does not appear to be caused by how you're using Outlook, nor our systems, but instead is a general Windows' Outlook issue.
Note that this process can take some time, so you may consider waiting until the end of your business day to begin it, and use the web client to perform searches in the meantime, by visiting your server address, inserting the beginning of your domain name where indicated here: https://yorudomain.zmailcloud.com
Rebuild Outlook Search Index
Go to File > Options and select Search in the left pane.
Next, click the Indexing Options button.
Indexing Options will open up; click the Advanced button. Note that this step may require administrator privileges.
Next, on the default Index Settings tab, click the Rebuild button.
Do note that while the index is being rebuilt, searches probably won’t work, so wait until the process completes. The amount of time it takes to complete varies depending on the number of emails, file size, and processing power.
You can see the status of the process updating at the top of the Indexing Options window. If you have other apps running in the background, then you’ll see “Indexing speed is reduced due to user activity.”
Once the rebuilding is complete, you are finished. Go back in and do some searches and see what kind of improved speed and functionality you get.