“Windows key stuck on Remote Desktop” problem.
Do any or all of you have ATI video card and a little ati icon on the tray?
Disable it!
Display Properties > Settings > Advanced > Options > “Show ATI icon on taskbar”
Solved the problem here.
I had similar problems back in the day with Terminal Services Client, ATI tray icon caused some freaky keyboard problems. After a month troubleshooting i found the solution. It seems to work in this case too.
Hope it helps.
Also: Opening the On-Screen Keyboard and pressing the windows key on the remote system worked for me.

A tavoli asztal lkiens (mstsc.exe) kapcsolodasa utan neha furcsa billentyuzet (keyboard) problemakat tapasztaltam (es sokan masok is).
ATI Hotkey Poller, Ati Tray Icon (atipaxx.exe, ati2vexx.exe)
kikapcsolasa regebben segitett meg a win 2k terminal services idokben.
Ha a Windows logo van “beragadva” nyissuk meg a kepernyo billentyuzetet (on-screen keyboard) a tavoli asztalban es nyomjuk le es engedjuk fel a win key-t.

”
I think the fact that we are almost a year past the first opening post and there is not even a technet article is sufficient enough to show you how much they care about this problem.

They don’t.
“