I am looking for a solution myself.
I lost all my messages when the upgraded phone to Android 2.2 (Froyo).
I called VZW and they said that is normal after a software upgrade, I'm like that's ******ed.
Happened to me as well. Since that has happened it seems as though the phone has come back to life after huge lag problem for days after the upgrade? Could something have been done to fix the update and also delete all messages????
Mine did this once a couple months ago. I was perplexed but it wasn't that big of a deal. Sucked that the message history was gone but I rarely review them anyways past the first week they are on the phone.