I did the install inside XP Mode and everything appears fine there. The application icons are in the C:\Documents and Settings\All Users\Start Menu\Programs location (I'm aware that per-user icons don't get ported back to 7). What else should I be checking?
The RemoteApp program shortcuts form the XP Mode VM should be available under
Start-> All Programs -> Windows Virtual PC -> XP Mode Applications on the host OS (Windows 7).
If you setup other XP, Vista or 7 VM's and enable the application publishing they will get their own similar shortcut folder on the host (named after the VM).