I have Firefox in my Start Menu, and searching "Fir", "Fire", "Firef", etc will turn it up. The search algorithm is just so bad that it ignores partial matches that don't start at the beginning of a word.
Try https://github.com/Wox-launcher/Wox
or http://alternativeto.net/software/everything/ or https://www.donationcoder.com/Software/Mouser/findrun/ or http://colibri.leetspeak.org/ or http://alternativeto.net/software/listary/?platform=windows or http://www.candylabs.com/approcket or http://www.launchy.net/download.php#windows
This was a popular thing ~10 years ago, not surprising that Windows didn't get it right. FWIW, MacOS also fails at this regularly with Spotlight, but Alfred is sometimes better. Wox seems to be the closest thing for Windows, and Launchy used to be the one the cool kids used.
It's super frustrating. When I search for "vlc", it gives me search results for VLC and instructions on how to install VLC, but it doesn't actually return the vlc.exe program that I already have installed damnit.