I forget what combination of settings does it but my Windows start menu now only searches the two start menu folders. It's perfect, completely deterministic, instant.

Trying to turn the app launcher into the magic "accio <anything>" bar was a huge mistake. You can have a second UI element for search, I promise it won't scare me.