I just encountered this issue and I’m on ios 12.2. Sprint is my carrier. I had tried all of the solutions above before finding this page. None of them work. I spent a few hours chatting with both sprint tech support and sprint worldwide support (via a WiFi connection). After giving up trying to find a resolution to the sms issue, they informed me that my plan included free data roaming. (I hope to God that’s actually true because i know it didn’t used to be.)
Anyway, I don’t know why I could send sms messages to my parents from Mexico to the US, but not to my wife here with me in Mexico. Every time I tried to send her a text, regardless of the iMessage and Send as SMS settings, I would get an error stating:

I.e. I tried iMessage on and off and send as sms on and off.
Incidentally, even though I had no icon indicating a data connection, I was receiving sporadic connectivity such as app notifications for emails and other communications but whenever I tried to use an app, I would get an error saying I wasn’t connected to the internet, such as:

Also, while I was able to call my parents, every attempt to call sprint via their 888 number immediately “call failed”.
Other things I tried: I made sure that I was sending messages to my wife’s phone number and not her iCloud address. I tried changing the phone type in contacts from iPhone to mobile. I tried adding 1 in front of her number. I also tried adding + in front of the 1. I tried turning off automatic cellular network selecrion and switching networks manually (settings->cellular->network selecrion->automatic).
Finally I discovered a workaround. You can send sms messages to google voice numbers and luckily, both my wife and I have google voice numbers. I had forwarding turned off on my GV account, so I had to turn it back on in order to receive, since using the GV app requires a data connection.
For anyone who tries to look for an actual solution, instead of a work-around, please note, every time you test a solution above, you have to make sure WiFi is off. Note also that Apple disabled the option to tap and hold a message to send as sms. It’s supposed to work automatically if you enable send as sms, but that only works if you have iMessage enabled and there appears to be a bug where if you turn iMessage off and try to message someone whom you’ve imessaged before, it refuses to send an sms in some cases. It converted to sms when I messaged my parents even though the thread had been iMessages up to that point, so I’m not sure what other circumstances are needed to encounter the bug. It could have to do with the location of the recipient, whether it’s a group thread or not, or... it’s anyone’s guess.