Consider offering email as well? With something like
SendGrid, you can probably push out all the emails nearly instantly. And if you ask users to provide their carrier, you can use the email-to-SMS gateways offered by most service providers (this seems like a fairly comprehensive
list, but I'm sure offering just the major US options would be fine).
I'm guessing you're using Twilio for SMS, which unfortunately does have that rate limit for non-shortcode SMS. This could serve as a fallback for users who don't provide an email and/or don't use a cell carrier with a supported email to SMS gateway.