It wasn't until 2.2 that the option to move apps to a encrypted location on the SD card was added, and even then it's an option that has to be enabled by the developer who released the app.
Newer phones these days have more onboard space and this shouldn't be nearly as big an issue. I upgraded to an HTC Thunderbolt on Saturday and it has roughly 2GB available for onboard apps.
Some apps can't move to the SD card, moving there means things like notifications from that app won't work any more. It's a terrible architectural decision, but my understanding is that it is a limitation of the VM, so they're stuck with it now.
I have a brand new Samsung Galaxy S II. It's a 500 GBP (800 USD) phone. It has 2GB of memory.
The first gen and second gen android phones (which may be less than a year old) typically have 128 and 512 MB.
So yes, having 8MB x (amount of apps that can't be stored on SD) taken from memory until you uninstall the app is huge.
I just hope that Google will see this and internally realize what's ACTUALLY broken in the Android Market and solve the real problems that exist.
I REALLY hope they see these comments and think "I sure wish there were a way to communicate with my users...." Which is a problem all of the Market publishers have been complaining about for over a year.