Keyboard keys not working or resulting in the wrong key

With intermittent problems you need to establish a baseline.

• Frequency of occurrence?
  • Does it happen once a day, once a week, etc?
  • Does it always start happening immediately after booting?
  • When it does occur, how frequent is the issue? So once you get your first symptom how often will you see symptoms?
• When it happens how do you clear it up?
  • Do you need to reboot?
    • If you do need to reboot, then try something else (like logging off and on) or just using it for a while, and see if it goes away.
  • Does it clear up on its own after a while?
• Are there any activity relationships?
  • Does it only happen after your roommate has used the computer (and maybe spilled something on the keyboard)?
  • Does it only happen on really humid days?
  • Is the temperature of the room a factor?
  • Is it more common at a certain time of the day?
  • Is there some software that you used right before it happens (maybe even before rebooting)?
• Does it happen in all programs, or only some?
  • Every time you boot up start notepad and type a sentence or two in there (depending on the frequency of the symptoms) and see if you see it happen.
  • If it only happens in certain software, or after using some specific software then you need to look into that.
  • Next time you see it start a command line window (run CMD.exe) and see if it occurs there. It actually talks to the keyboard a little differently.
    • If you get it in a command line window then it is more likely driver or hardware.
    • If you don't get it in a command line window then it is software running at a higher level (user launched application).

If you don't know the pattern (if there is one) then it will be hard to know if you have fixed it unless you find obvious hardware or software that is causing the problem. If it does have a predictable pattern then try booking a Live Linux as was suggested - then you can test the required number of times (or usage pattern) to see if the problem reappears or not.

Hardware

It sounds like you eliminated the keyboard or the USB port, but it could also be the motherboard. If booting to Linux can reproduce the problem, then it is your motherboard or BIOS. If not then we know it is related to your software.

Malware / Virus

A malware and virus scan is a good idea. I used to do tech support and it was surprising how often someone would have some really weird behavior, and we suggested it was a virus and they would deny it, but then when they ran a scan (with updated signatures) it would return positive (and usually a pretty heavy infestation).

User Accounts

You also might try creating a new user on XP and see if that user gets the behavior too. If not then it is probably software being ran on the other user account. Slowly start installing it for the new user until you see which one causes it.

Software

Download WinPatrol (it is free) and look at what is running on start up. Then start disabling things and see if you can disrupt the pattern.

Environmental

If I were a betting man this is what I would put my money on. I remember one time I was helping a guy on tech support and I suggested something was spilled in the keyboard (most common cause) and he swore that no one would ever spill anything on the keyboard. Then after we troubleshot pretty much everything else software related he picks up the keyboard and water pours out on him. Turns out the keyboard was sitting on the floor near the kitchen, and the kids had spilled water in the kitchen, which flowed out and into the carpet, which got in the keyboard.

It gets better. After he poured the water out he discovered the keyboard was infested with ants. At this point he was getting really grumpy with his wife and kids about the no food or drink near the computer rule. I told him that tech support didn't support ants in the keyboard. He was going to try running it through the dishwasher.

You could try some bug spray as a preventative measure, but your mileage may vary. Even though you replaced the keyboard, the ants may have come back due to crumbs near by.

I would suggest further diagnostics: try booting the computer from a USB distribution of GNU/Linux such as Slax or Puppy Linux. Does the keyboard work with that?

Also, try the on-screen keyboard built into Windows and, if those OSes don't work with hardware keyboards, the Gnu/Linux distro you choose. If the onscreen keyboards work but the other OSes don't, it's a hardware problem. If the other OSes work and the onscreen keyboard doesn't, you have a strange software problem and I can only suggest reinstalling windows.

PS. I know about language settings (and personally use dvorak) and this isn't it; that wouldn't cause random problems at startup, as the keyboard is always the same at startup.