I seem to recall that you can send an email message to sms using the phone number and the correct domain, example:
5143330000@fido.ca
You have to know the carrier of the person you are texting however, as well as their phone number. I believe you should be able to find the list of domains by doing a Google search, I recall I had found it once upon a time when trying to reach my daughter instead of calling long distance... Otherwise you should be able to find it on the cell company website site by searching for "email to sms"... If I recall correctly the cell user just "replies" and you get their answer by email.
Edit: found more details:
http://en.wikipedia.org/wiki/List_of_SMS_gateways
How to:
http://mob.conduit.com/d8221e2f-6894...mail-to-sms%2f
No need for an app or for having the same app for both users.