I use the Win-key+[start typing] search all the time, but I also used it in the XP era. Only then it was a third-party app, with order of magnitude more customization and control. I actually have a worse experience now, but it's just above my tolerance threshold so I don't do anything about it.
Wouldn't it be below your tolerance threshold then? ;)
I feel during XP times it was basic string matching, and sometimes I miss that. At one point on linux they also started matching on description text, but then application maintainers started to add keywords to their description text for their app to rank higher, which again made it worse to find whatever you are looking for.
I've navigated systems this way for so long, I forget people do it any other way. Someone from IT had to remote-connect to my system yesterday to do something, and to get to the control panel they opened the start menu --> clicked the Settings gear --> Bluetooth & devices --> Scrolled all the way to the bottom of that page to click "More devices and printer settings", which then opens 'Control Panel\Hardware and Sound\Devices and Printers', then clicked "control panel" in the address bar. I was baffled. Winkey --> type "CON" --> hit Enter is so many fewer steps.