Q:

Why is "insufficient storage" wrongly reported when installing an .apk via adb?

I have an HTC Desire running Froyo. It is not rooted, nor have I installed any custom ROM.
I get an "Insufficient Storage" error when I'm trying to install an app via adb/eclipse. The .apk is only 300KB, and the phone reports 14MB free of internal storage, and 2.2GB free on the SD card. (I have just uninstalled a few large apps to make sure there's plenty of room.)
It is obviously completely wrong. There's easily plenty of room in the 14MB of internal storage for my 300KB app.
What can I do to fix it?

A:

At least on my phone, it seems you need way more available space thanthe size of the app you are actually trying to upgrade. In my case it seems I needed to have at least ~13MB free space to upgrade anything at all (even for 500KB apps).
Some tips to free space:

Go to Settings, Applications, Manage Applications, click "Move to
SD card" on the ones that have that option.
In the same list, also click "Clear Cache" on all your apps.
Your browser cache can not be cleared here, so open your browser, go to Settings, and click "Clear cache".

In some cases I have also been able to manually update apps one at a time when "update all" fails due to insufficient storage.

A:

I discovered that K9 Mail was keeping 25MB of cached data on my internal storage. I changed it to use the SD card, and this cured my immediate problem of being unable to install a tiny app.
It doesn't explain, though, why Android was reporting an insufficient storage error whilst simultaneously telling me there was 14MB free on internal storage. Oh well. 

