There's http://ad.ly. That's started by some former MySpace/Fox guys. But to offset $0.03 per message, you'd need to get $30/cpms. That's not impossible, but you could be sending your users ads for services they might not want. Ringtones and whatnot.

You're right that email gateways are risky. They're not consistent and they show up as from random consecutive numbers to your users.

I suppose it's not possible to utilize the Twitter API for this?