I am happy to say, that after scouring the web for days, and trying a lot of wrong information, I finally figured out how to fix this.
It's real easy. All you need to do is remove any *.apk files located in the /cache directory on your phone (did not even need to remount- though I did it as root just in case).
I never did figure out why only some apps will have this problem or how the problem first comes about, but I have successfully done this twice and have since been able to install/update files that had this error before.
Update (3/3/11): OK - After scouring the Internet for over a month I finally figured it out. My info above was only part right. The problem is specifically with ROMs/Kernels that move the dalvik-cache to the /cache directory (HTC puts it in the /data dir).
In any case, when it's in /data, it is using app space, and therefore you usually run out of app space and know about it. However, because this is in /cache, you don't really know what you are using. As you load up on apps, your dalvik-cache grows, and since these apps need the .dex files in the cache, even if you clear your cache, it will just get re-created.
the /cache dir is also where the apps are temporarily stored while downloading from the market. So....
1. If you are getting immediate download fails, that means that your cache is so full that you don't even have space for the temp file.
2. If you get "Invalid Package" that likely means that there was not enough cache left to install the .dex files (the download is also taking up some of this space).
Unfortunately, the only way to fix this is to either remove some of your apps, or move your cache to your SD card.
HOWEVER, I found this great app on the market called Link2SD, that allows you to only move select apps to the SD card, and you can also move the dalvik-cache files associated with these apps.
see this thread for specifics: http://forum.xda-developers.com/show...28&postcount=1
it lets you select which apps to move. You will need to create a new partition on your card, though.
So far results have been great and I can finally update the 30+ apps that have been stuck for me for the last 2 months.
almost forgot, if you adb shell or use terminal emulator, you can type "df" to see how much space is left on all your mounts.