I was researching what people do about keyboard mappings when using virtual machines or remote desktop connections from their Macs, especially when the other system is running Windows. Different software packages map the keyboard differently and some even have different modes that provide different mappings. Now whenever I see a Windows desktop, I have no idea what keys to press anymore.
My research led me to KeyRemap4MacBook. It comes with a kernel driver that lets you map any key presses you like, in one or more applications, on one or more keyboards. All this power is configurable in XML and selectable through a preference panel applet.
I haven’t fixed my Windows keys yet (partially because I realized I might want to keep Alt as Alt, instead of using Cmd), but I have added a binding to switch keyboard layouts using a combination similar to the one used on Windows: Command + Left Shift (or Shift + Left Command, if you prefer). As far as your muscle memory is concerned, this maps to Alt + Left Shift on a PC keyboard.
I switch between the Finnish and US English layouts, so I also needed to add support for the Finnish input mode. This is why I added the bindings in checkbox.xml instead of private.xml (see patch) — you could add similar entries in the latter file for the input modes you need.
Update: My patch has been merged upstream and is included in version 7.2.47 and later.