HTC Incredible from Verizon, running v2.2. I love my phone. Really. It's my Little Buddy. But I've had this problem, off and on, for years. It's annoying as hell. I've found a few ways to fix it. These are all mentioned in numerous other threads, here and elsewhere, but these are the methods that worked for me. By "worked", I mean they've made the problem go away temporarily, sometimes for several months, but the stupid erroneous error keeps coming back. Some methods are less painful than others, but all include some loss of data or worse. Seriously, HTC, please fix this!
#Factory_Reset - I mention this one first, but it's really the last resort, in my opinion. It always works, but it's a pain in the ass. I use #AppBrain, which makes it relatively easy to restore my applications, but resetting all of the settings everywhere is a royal pain.
Go to Settings, SD & Phone Storage, scroll to the bottom, hit Factory Reset, answer all warnings affirmatively, wait for your phone to perform it's own brain-ectomy, wait for it to reboot, and, yay!, you've got your old brand new phone back. Have fun putting EVERYTHING back the way you want it and
Re-installing all your apps.
#Clear_Caches - Clearing Caches is pretty safe. You won't lose anything too valuable - maybe some saved user ids and/or passwords, nothing serious. WARNING! If you Clear Data, instead of Clear Cache, you may lose more valuable stuff like settings, saved scores, etc. (If you're willing to do that, you may want to consider the #Factory_Reset mentioned above).
Go to Settings, Manage Applications, select the All Applications tab, and find the setting called, "com.htc.socialnetwork.prov...something_or_other" (I can't see the whole name on my phone, because Settings don't display in landscape on my phone). Clear this cache. Clear any caches for any other applications too. Little harm, couldn't hurt. Try clearing the Messages application cache too - I think this worked for me once. If, after clearing caches, the error icon doesn't disappear, you'll need to try one of the other methods.
#Delete_Messages - I'm talking SMS/MMS messages here. The stock Messages app. You can guess what you'll lose with this method. All your message threads will be gone. Do you care? Anything real valuable in there? Probably not (for me). You decide.
Open the Messages app. Make sure you're on the All Messages screen. Tap Menu, tap Delete, tap Menu, tap Delete all Threads, tap OK. Wait and see. Did the error icon go away? Works for me pretty well.
You can try to messing around with the other Messages Settings, too. Couldn't hurt.
#Keep_Email_Very_Tidy - I'm talking the stock Email app here (not the Gmail app). If you've got a lot of emails on your phone, Try getting rid of some or all of them. Make sure you empty the Trash folders, Sent Items Folders, Drafts Folder, etc. You may also want to delete all the accounts you've configured and re-configure them - just to give yourself a clean start. This worked for me once. Since then, I keep my email very tidy. I keep email messages on the phone only as long as necessary. I'm actually a bit obsessive about this, now that I think about it. And, yes, the stock Email app sucks out loud. I've tried using others, and some are definitely better than others, but none have prevented the problem from reoccurring (permanently).
I've read that others have had success by abandoning the stock Messaging and Email apps, and using third party apps instead. No doubt that the stock apps are pretty bad. And I wouldn't be surprised to learn that (at least one of) the root-cause(s) of the problem lies somewhere in these applications, But I've tried a few, the most popular ones anyway, and none have permanently solved the problem (for me).
I hope this helps. Good luck.
Please, HTC, fix this problem!