I've spent time on XDA developers working on the HTC_IME keyboard. It's not a true multitouch implementation. There's some pseudo multitouch tricks HTC uses here and there so you can type faster, but that wasn't my main reference. Perhaps the Incredible makes things easier and has upgraded the soft keyboard.
The stock Android keyboard LACKS multitouch completely. Also I believe Android registers keypresses on an key UP event (when you let go). Thus, it's very hard to implement multitouch. HTC's IME keyboard uses a key DOWN event where when you press one key it registers. Works a little better if you can tweak it and combine with a key UP event to bring some pseudo multitouch capabilities which is what HTC has done, but the bottom line is Android's soft keyboard itself still lacks multitouch. I've played with the Hero, Droid Eris, Droid, and Nexus One (the latter 2 very extensvively).
Here's the developer explaining it:
It works like this: Press one key with one finger. Press second key with second finger before releasing the first. Now release first finger then second. This is registered as one down event, some move events and finally one up event (Not true multi touch!). It works like this: Press one key with one finger. Press second key with second finger before releasing the first. Now release first finger then second. This is registered as one down event, some move events and finally one up event (Not true multi touch!).
Now this is HTC_IME, so unless you're running a Droid Eris or Hero, you don't get this unless you've been applying the HTC keyboard from XDA developers.
Your true multitouch solution is to look at Smart Keyboard Pro. I've been using HTC's IME keyboard since day 1 and while it's better than the Android keyboard, it's no iPhone keyboard yet.
BTW, you don't need to hold the shift button down to get a capital letter. Isn't it just a tap once to capitalize the next letter?
And this is something I want implemented. I'm glad of the Incredible does get true multitouch. It's something we're all waiting for, but what I'm saying is that Apple has implemented a beautiful soft keyboard and the implementation was nearly flawless. Remember when the G1 lacked a soft keyboard? And the Android stock keyboard is only marginally better than say a resistive screen without multitouch. So yeah I'd love to see an improvement, and if what you said about the Incredible is true, then great. However, similar to what the OP said, I'm still amazed at how Apple can deliver such a quality experience when it's making the first stab at a lot concepts. Android plays catchup on the other hand for a lot of these things.