Yeah, that customer service rep sounds like (s)he didn't know what he was talking about. Having inadequate storage space would only be an issue when receiving, and thus storing, messages; not sending. It sounds like an issue with your modems/wireless radios. Try going in to your local VZW branch and asking them to reflash your phone with the most up-to-date modems. Do you have any problems with making/receiving calls, or any issues with data? It might possible be the Messaging app itself, although that's unlikely. Try installing something like Handcent to replace the Messaging app and see if that fixes anything.