nevím jestli funguje už v xp:
REGEDIT4
[HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\Policies\Explorer]
"NoWinKeys"=dword:00000000
ale pokud samotná klávesa "win" funguje, jen zkratka win+r ne, pak bych nejdřív odviroval/odspywaroval.