The thing that raised my eyebrows was that my work laptop had this issue. And this is a serious work laptop, managed by a large & conservative IT org. I'm so locked down with GPOs/McAfee/Zscaler/Cylance/always-on-VPN that I have trouble opening my normal applications that I need for my job. And then Microsoft comes along and breaks stuff locally on my machine by changing something on their servers. So all the firewalls/VPN/proxy/cylance smart rogue program detection failed to do their job...
And to top things of the issue did not fix itself, as of Friday afternoon my start menu search still did not work.