Out of curiosity I just found that this is a known Verizon problem. Suggestions from a Verizon rep:
"I would attempt to clear the cache on the messaging app and start there. Clearing the cache of the messaging app can be done under Settings> Applications> Manage Applications> All> Messaging> Clear Cache/Data/Force Stop.
Warning: This will likely remove your email accounts and erase all text messages.
If none of that works, you can try 1 of 2 things: 1) Master Reset.2) Try a 3rd party text messaging app. A search in the Market for "Text Messaging" should yield plenty of results."
Others suggest installing a third-party texting app or wiping the cache partition all together. I found this here:
https://community.verizonwireless.com/thread/561438/ for common Droid X issues.