Same here, I did all that, and absolutely nothing.
It doesn't matter what I look for: flagged items, items with certain categories, or plain old messages from a certain person. It worked perfectly after I first installed Office 365 a few months ago and then magically, this month (March 2021), it stopped working. Completely. None of the actions (re-indexing, removing profile, etc, etc) change that.
I am considering moving back to Mac Mail, because this is unacceptable for ultimately a mail / database tool. What I find most frustrating is that this search problem in one or another form seems to exist for over a decade.
Microsoft: solve this ridiculous bug! I've wasted well over three hours on it