I interacted with MS's dedicated Outlook for Mac support team via the Contact Support feature on the Help menu in Outlook. I was told to do the following,
Quit Outlook completely and then open Terminal on the Mac and then copy and paste the command
sudo mdutil -E /
It would prompt for your Mac Password please enter it and wait for it to complete and then give it some time and then re-launch Outlook and check if that helps. If you still face issues.
Quit Outlook completely by click on Outlook Menu > Quit Outlook and then try the steps
1. Choose Apple menu > System Preferences, then click Spotlight.
2. Click the Privacy tab.
3. In Finder:
a. On the Go menu click Go to Folder...
b. Copy and paste the following location into the "Go to the folder:" dialog box and click Go:
~/Library/Group Containers/UBF8T346G9.Office/Outlook/Outlook 15 Profiles/
4. Drag the ‘Main Profile’ folder to the Privacy tab. Once added, remove the folder, and Spotlight will re-index the folder. Note: You must perform this step for any additional profile folders you may have.
See the following article from Apple to learn more: https://support.apple.com/en-us/HT201716
This appeared to work - messages were appearing in search results. But unfortunately, the fix was short-lived. Newer mail is still not appearing in search results. (I can be looking at a message just received in my inbox, search for it, and get no results).
So there's still a problem. But at least I temporarily have some kind of search capability.
I have posted this back to the Outlook Support team and will update this thread if they respond with helpful suggestions.