I had the same problem on my Compaq 2199US under Fedora Core 2 (test 2, I think). I have a custom 2.6.5 kernel, but I strongly suspect your problem might have the same cause as mine(ultimately, I think it's a busted BIOS problem). After a careful reading of the dmesg output, I found a message that suggested ACPI could cause problems. It suggested either turning it off altogether (which is a lousy option, but if all else fails, I guess you could try that too), or just passing the option:
to the kernel at boot time. This did the trick for me, and now I'm happily typing away at normal speed without lost & transposed keystrokes. I didn't look into it too much, but I'm guessing that ACPI controlled PCI must have caused some problem with an IRQ associated to the keyboard.
Hope this helps (or, I hope you had already solved the problem).