Our best estimate is that some carriers who provide the email-to-text service we use for the text messages look at our mail server, which sends over 40,000 emails per day currently, as a potential spammer. The emails are being sent out (you can see them in the Email Log within the System Administration module) and they're not bouncing back (we can see that in our mail server logs) - they're simply not being processed by the carrier for whatever reason. The more customers of that carrier who report the issue, the more likely they are to do something about it.
A past suggestion we've had from one of our more local carriers is that the name of the email address being used by the site to send out the messages may have an impact. When we launch a new site, and create a domain on our mail server, we use "admin@" as the primary email user and set that to send the mail out from the site. So what you might want to try is creating another email user with a different name, say "notifications@" or "noreply@", and then use that address for sending messages (System Administration -> Email Administration -> Email Settings).
If anybody who is having delivery issues would like to try that and let us (and everyone else know) if that works, that would be great.