This problem seems to have been around for a while yet is not acknowledged by Microsoft and none of the forums yet have solutions posted that work despite it being very well communicated. As the push for O365 users to upgrade to Office 2016 is starting, this might become a big headache for many people.
It is simply that the search function does not work in Outlook 2016. It works in safe mode but not in normal mode, even with all add-ins switched off. Rebuilding the index or removing Outlook from the Windows Search service scope does not work.
If anyone has discovered a solution to this Microsoft bug - please, please post it and help put people out of their misery.