What happens when you do the plain ol' ctrl+alt+del lock? Or when you set it to lock coming out of your screen saver?
This may sound like a weird question, but maybe the windows key is stuck or something...
Maybe you could try hitting Fn+NumLock and then Fn+NumLock again to restore functionality OR good ol' ctrl+alt+del. You may have tried some of this, but you'd be surprised how flaky the Fn and Win keys are at times. Also, (and I'm going to suggest this just IN CASE you haven't checked, though I'm sure you have).... Have you done a ctrl+alt+del to check what processes are running? Maybe there is some type of funky process running that is activating once it comes out of lock mode.
Good Luck. That's all I can presently think of to suggest without more info.
err....wait a second (2nd edit) NOD32 - Which version? 1.0 or later? As a test disable NOD32 (if you are a security freak, just disconnect from the network/internet by pulling the plug or disabling your wireless connection) do your win+l lock and see if the issue persists. Read their FAQ http://www.nod32.com/support/nodfaq1.htm
Not particularly addressing your issue, but is involved with it perhaps if it isn't just general win key funkiness.
Once again, hope this helps.