I had the same issue.
14G free on SD
5G free on internal storage
and 500M Memory Free.
Talk to Verizon. They said they need to do a Master Reset. I told them to shove it. Then they sent me to HTC Support 866-449-8358. They said that each carrier writes there own messaging Apps.
Long and the Short is the Verizon Messaging Apps Sucks and doesn't know how to compute storage space.... So ****ty that you can't even view a message that is already on the phone.
The Fix...Dont use the verizon Messaging app Download "Handcent SMS" instead its free and so far not bad.
Use Handcent SMS