I use a nice little utility called Launchy[0]. It is invoked by Alt-Space (or whatever shortcut you like), is lightning fast and finds the right application 99% of the time. Based on your problems, I think it could be worth checking out.

[0] https://www.launchy.net