Your problem is related to Virtual PC, not Start Menu related. VM=Virtual machine. What you are using as "XP Mode" is a Virtual Machine running on Windows Virtual PC software which is available
only for Windows 7. Okay, try this:
1. First shutdown Windows XP Mode.
2. Open "Windows Virtual PC" from the Start menu.
3. Select 'XP Mode' in that folder and click "Settings" button on the toolbar.
4. Go to the "Auto Publish" section and make sure the option is checked.
5. Start XP Mode so any shortcuts will be auto-published to the Start Menu folder.
XP Mode shortcuts most definitely work for me this way. They show up in %appdata%\Microsoft\Windows\Start Menu\Programs\Windows Virtual PC\Windows XP Mode Applications