Just an observation, but maybe what you describe was going on before Lion. You said it occurred on VMWare 3 as well, though I don't know what you upgraded first. My keyboard problems were intermittant. When they first started happening they weren't that noticeable. Sometimes the keyboard would miss a key I'd pressed, and I thought I just wasn't pressing hard enough. So initially I blamed myself. It was only later that the problems were getting worse and I realized it couldn't just be me. It's something that can creep up on you.
When it happened to me, I was running Leopard and VMWare Fusion 2. I was using Mac apps. most of the time, but I'd see it in both Mac and Windows apps. What fixed all of these problems for me was taking my MacBook in to an Apple store and having them replace what's called the "flex cable," at least on my model of MacBook, which I got in 2008. Though it might be a different problem given your model, so it might be better just to tell them what's going wrong. The flex cable is a cable inside the MacBook's case that connects the trackpad and keyboard to the logic board. It has a chip embedded in it that has been known to go out, causing the problems described in this thread. The price for the cable was $14 (though I did it several months ago). The part that's expensive is the bench fee they charge for doing it, $40. When it comes to repair work of this nature, this price is pretty normal. If you get it in to them under your warranty, this kind of repair is covered by it.