I am extremely happy to report, that my Outlook search suddenly and finally started working normally again, in the early morning hours of May 31st! Wow.....I had forgotten how "friction-less" Outlook searches used to be, before the Outlook search bug started to affect me around 3 weeks ago! I now need to check if my clients that were affected are now fixed as well.
I can't completely relax regarding this though, because strangely, shortly after I started getting affected by this Outlook search bug 3 weeks ago, the problem actually went away for about 2 days, before the problem came back again for me for the long-haul 😞 Hopefully it doesn't come back again!
I *still* would really love to know what the fix was, *especially* since it was a multi-staged fix. HOWEVER, the most important thing is that the bug is now fixed, which it seems to be for me, for now. Thanks for everyone's assistance here, abdias_ruiz & Travis_78, and for Microsoft eventually fixing this problem!