I deal with this type of malware for a living. Once you know what it does it's quite quick to clean up a system.
Fist off, it's foolish and counterproductive to try to remove malware by using the OS that's infected. Boot to a live CD (like BartPE so you can mount the registry) and at the very least disable it from startup. From there feel free to boot to the OS and repair the damage.
The start menu is indeed moved to the user's Temp folder. In detail:
smtemp\1 is the public start menu
smtemp\2 is the user's start menu
smtemp\3 is the public desktop (I think, I've only seen this folder once)
smtemp\4 is the user's desktop
It also disables the listing of recently used programs in the start menu and un-pins everything. It's easy to turn that back on.
The following is a terrible idea:
attrib -h /S /D C:\*.*
as it will unhide everything on the computer.
It's quite easy to instead just select all the profiles under \Users\, go to properties, uncheck hidden, and apply to all sub objects. Afterwards, go into each profile and rehide only the top folder of AppData and all of the files in the root of the profile (things like ntuser.dat). In XP there are a number of other folders under the profile that are hidden by default. Reference a known good computer to see which ones.
It may also set some group policies to disable the desktop, the task manager, and disable changing the wallpaper. Delete these.
The particular malware that does this does not alter .exe associations, but if you need to fix those, there is a far more reliable free tool from Kaspersky called AVZ. The option is under File -> System Recovery. (Tip: you can rename avz.exe to something like avz.com so you can run it. Or manually fix the association for .exe and let the tool fix the rest.)
Another spot to look out for is IFEO debugger entries. Look under:
HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows NT\CurrentVersion\Image File Execution Options
Inside you will find keys of image names (like iexplore.exe). Under each key you may see a string value called Debugger. It's data will be set to the path of the malware that's infected the computer. If such a key exists, the 'debugger' will be launched whenever you try to execute the specified image.
That about sums it up for all of the 'modern' 'viruses'. Quite pathetic. The only reason these things work is because people are tricked into letting them through UAC. The new Mac infections function nearly identically. They require that the user enter their root password for them to install, and all they do is put themselves in the Mac's startup locations, so they're even easier to remove.