I don't even know how to start here.
What is the format for shortcut files?
How do I retrieve the location of the start menu programs in XP and Vista?
Is there any funny stuff I need to be aware of with Vista?
funny stuff with vista: it sucks
:)
XP and Vista are different.
XP is quite simple, there is an "All Users" Documents and Settings->Start Menu folder which is combined with the user's Start Menu folder.
Vista is much more fiddly and uses an XML based structure but with wierd bits, for example many games now don't enter the start menu at all but now go directly into the "Games" folder (something I found confusing when I stared using Vista).
I would use an installer program to do the deployment work for you, it's not worth the hassel of doing it yourself and there are plenty of free install programs that do work with XP and Vista.
Darkheart
games only go into the games folder if they passed the "Games for Windows" testing, otherwise they will not.