It's usually a carrier thing, not a phone thing, if some send and some don't. See if your carrier can trace a "not sending" message if you go to the store and send a message that won't send. (Then at least they'll know where it's being blocked and Networking or Engineering can work on why.)