Comment 10 for bug 2195

"touch /path/to/desktopfile.desktop" at the end of the package installation. Or make it possible that it's installed after the executable.

I'm not sure that Mark will accept a patch which looks again if the executable is here after 10 seconds, but that's the only gnome-menus workaround I can think of.