[Droid Incredible General] Solar257:
I call this a new recommendation because I haven't seen before. It comes from an HTC service representative, and aside from factory resetting the phone and looking at app size/cache sizes (not app data) for various apps via Settings > Applications > Manage Applications > All (menu, sort by size), I was still "normal." The largest app on my phone was the FiOS app at 14.6MB. After that, everything was smaller. I had 451MB remaining in my application storage, 5+ GB internal free, 11+ (of 16GB) free on my SD card, and ~90MB available in cache space. In essence he told me that the low space error message was generic in nature and could be indicative of an app running out of "space" instead of my phone running low on space.

The recommendation the HTC support person gave me to try today was clearing my browser cookie data, cache, and history. The reason we went to this step was because I had noticed and mentioned to him that, with only one window open, the browser was using ~50MB resident. This was an observation I made after looking at the Internet app resource usage numbers via the System Panel app. The odd thing is that this memory usage didn't show up in in the Settings menu. Clearing the caches is done from the settings menu of the Internet app (from within the browser app, tap the 'menu' button on your phone and then scroll down to "Privacy Settings"). Now my Internet app uses ~14MB with one window open. After doing this step, and without a restart, my issue with the low space error went away (hooray!). It's a basic recommendation I know but in the searching about this error I have not read it before and actually read the HTC was denying the issue existed. I should note that we talked about the mail app, however there was noting too out of whack as System Panel showed it as using 12MB and it had no cache I could clear.

Another recommendation I received was managing the number of messages in each of my threads in the default messaging app. Essentially the more messages I have the greater the possibility that I run into an issue of a generic message sending failure. I asked a second representative about the thread limiting feature (under settings of the messaging app) and the fact that I had backed up and restored my text messages before, and now they were not being properly managed (i.e. I had 152 messages in a thread when I was telling my phone to keep 130). The second representative was the one who was conducting my customer satisfaction survey at the end of the call. He put me on hold for (at most) two minutes and then came back with an Incredible and told me that the feature is designed to keep the last 100 messages on my phone should a cell provider decide to clear text messages from their server. He also advised me to keep an eye on Dialer Storage, and that if it gets above 15-20 MB I should clear the data. He warned me of the importance of this app as it stores some of my email account info (if I remember correctly) and text message cache, so clearing that app does not come lightly. As I stand right now my Dialer Storage is ~7.14 (with 6.84 in data) when viewed in Settings menu. Though my Messages app says it only has 824kb or data and 2.2MB of total space in the Settings menu, it stands at ~18.5MB in the System Panel app.

I've noticed that after getting one of my threads down to 100 messages (my new limit) it's now staying at that limit at least for the one thread I tried it on. So maybe the thread limiting feature does work. I hope this info helps someone else with this problem and does not have cache issues that show up readily when looking at apps in the Settings menu.

P.S. I also asked the first representative about Push Messages in the messaging app. I was told it has to do with supplemental data that can come along with email accounts that use the POP and IMAP mail types. He also told me that it's possible that some carrier messages can end up there as well.