Doesn't the built-in messaging program use SMS? Take a look
here for Palm's description. The big question is if Verizon has disabled that so you subscribe to their paid services. I don't have VZW so I don't know...
When I had my 650 I used Toccer, a great program, but I believe that used data.
SteveTaz
EDIT: If you are holding out for an IM format that uses text messaging I think that will be a hold up. They work off data and I think that is what allows for things like the Buddy List. I am not a text expert though.