It sounds like you're trying to run an executable that's on your PATH. The start menu search does not apply fuzzy search to locations in the PATH environment variable (reasonably so, most of it is either going to be command line tools that need additional arguments and spawn a console window that instantly disappears or just junk that most users don't care about).

If you want fuzzy searching to work, add a shortcut in the start menu for runemacs by placing the shortcut in %APPDATA%\Microsoft\Windows\Start Menu