Encontrei o problema no meu laptop, na minha área de trabalho e na área de trabalho, por isso obviamente não é o teclado (ou são todos os três). Eu geralmente vejo quando estou usando o desktop remoto.
Eu encontrei um thread sugerindo que é um bug relacionado ao uso do Win + L para bloquear sua tela e deve ser corrigido no Vista SP-1, mas obviamente, não é.
Descobri que apenas pressionar a tecla do Windows uma vez parece resolvê-la para mim, até que isso aconteça novamente.