I don't remember the last time I really used the start menu. My normal workflow on Windows is the same as on iOS:
Focus or open the search box ("Windows-Key" on Windows, or swipe-down on iPhone X) and type the program I'd like to start. Works pretty well on both systems, and normally the first letters are sufficient.
That's what i used to do until it was not possible to disable the bing search anymore. This + the fact that searching for a program was quite inaccurate (it will sometime not find it, or do weird stuff like "not" will find notepad, "note" wouldn't, "notep" will find it again). I found myself opening edge all the times searching for things i don't want to search with a search engine i don't want to use.
I never found a way to disable this advertisement for bing.
That was the nail on the coffin that made me change operating system and I really don't miss windows 10.
Also, it frequently manages to find a new, undesired, match just as you're about to click the the thing you actually wanted, thus repositioning the tiles and causing you to launch the wrong thing.
This is what happens when you let WebDevs work on your UI.
I don't know how many times I've needed to fix something with a user's display settings and hit Windows Key and started typing the word "display", only to end up with an app recommendation instead of the damn system settings! Oddly, if I just delete the last letter and search "displa", I usually get what I wanted. Windows 10 is so very frustrating.
I have bing search disabled, so it is still possible, but don't ask me how I did it. The Problem you describe still persists, though. So it seems to not really be related to bing search that they totally fucked up the start menu search. It's a disgrace how bad it is.
To be honest, i had managed to disable it prior to some of the big updates.
After having to reinstall windows from a newer medium including those updates, i wasn't able to disable it anymore.
From memory, it was just an option in the start menu settings that has been removed now.
I dimly remember it being more involved for me than that and probably included group policies + registry. But it is gone for now and has not come back with updates. I am not sure I ever do a new install of windows 10 on my home PC should the need arise. For me, the signs point to Linux more with every new "feature" MS builds into Windows 10 and the only thing really holding me back still is gaming.
I've created a dozen or so of entries myself in the HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\App Paths registry key and i also got a few in the taskbar.
For instance to start firefox i can do windows-key + 1 (taskbar) or windows-key+r+ ff + enter (app path registry key)
Focus or open the search box ("Windows-Key" on Windows, or swipe-down on iPhone X) and type the program I'd like to start. Works pretty well on both systems, and normally the first letters are sufficient.