Comment 1 for bug 186961

All right, I have just taken a quick look at the source and found the following:

The function "get_all_applications" (gnome-panel/panel-run-dialog.c:817) appears to get the list of applications from the Applications menu. Indeed, adding "gvim" to the menu (in System->Preferences->Main Menu), solves both problems, i.e. the "Run Application" dialog now includes "GVim Text Editor" in the list of known applications and displays the icon when I enter "gvim" in the text box.

I am leaving this open for now as I am uncertain whether getting the list from the Applications menu is the Right Thing to do when the menu does not contain all known applications (file-roller is another example of an application that is not included in the menu by default).