Vista Start Menu won't launch some applications.
As strange at it may seem, this is often caused by a bad Shell Extension, which is mistakenly handling the launch request.
I had this happen on Vista, and found the NirSoft ShellExView was just the thing to fix my issue. It is freeware and if you don't need it, you won't even know what it is, but if you need it, you really need it.
My problem was that any program in the start menu's recently used or pinned area would not launch if and only if the shortcut didn't include the path (items where the "Target" was simply the application name). By disabling all shell extensions via ShellExView, I could launch such applications (Safari, Microsoft Office, etc). This proved my theory that it was an extension.
Next, I sorted by Filename, and enabled everything in %systemroot%\system32, hoping those were "good". They weren't, so I disabled them and enabled everything else. We could launch again.
From here I started a block of extensions and tried to launch, moving on until it failed again. I disabled that block and enabled everything else.
Now I have a binary search to perform. Enable about half: if it works, great, if not, disable and enable the other half and subdivide again.
Following this process, it was found to be the MTR.ShellExt.LaunchContextMenu, described as "Microsoft.NET Runtime Execution Engine" version 2.0.50727.1434 (REDBITS.050727-1400).
I had recently installed a program that I recall seeing the Microsoft runtime being installed with, so I suspect that this runtime somehow caused the problem described. Disabling this extension restored my launch capabilities and has not affected other programs or even the program in question that uses the runtime.
I won't name the program because I'm not 100% *sure* this is the cause at this time, but I suspect any program that installed mscoree.dll as a shell extension may have the same problem, as I found other instances of the exact same symptom (launching works for items with a path, but not just a registration of an application).
Thank goodness for an excellent utility (ShellExView) to help figure this out: with nearly a hundred extensions to worry about, this would have taken forever without it.
EDIT: Using another feature of ShellExView (open CLSID in RegEdit), I was directed to the program that installed the hander. MindSystems' ThemeReader is a program that summarizes documents, and I notice that with this disabled that the context menu for ThemeReader is gone. I believe the problem is caused by the fact it applies itself to the wildcard file extension ("*") and thus tries to activate for start menu shortcuts as well as normal documents. Nevertheless, I can always manually launch it when necessary, and in the meantime the tradeoff of everything else launching is worth it.