A good friend of mine John Dabnor alerted me to this new company Teleflip that allows easy sending of SMS messages to any cell phone.
Just send an e-mail to firstname.lastname@example.org, (i.e. email@example.com) and it will be delivered. You dont need to know the service provider.
There may be some issues related to LNP or local number portability meaning that if a cell phone ports from one provider to another it may take some time (Their FAQ says a few months) until their database is updated.
I havent tested the service extensively but I did send I some messages to some invalid cell numbers and they bounced back which is good to know. I was able to get a message through to a T-Mobile phone.
The service is free. Let me know what you think.