This behavior just started randomly today, with no discernible connection to an iOS update. Though it was around the time I began to sync my iMessages to the cloud.
Using my MacBook iMessage, which traditionally of course has worked sending to both Apple and non-Apple users through the Messaging relay), I craft a message to an Android user. It first sends as an iMessage.
My first thought is, cool, so-and-so now has an iPhone. But then I come to find they don't receive my message. When I try again later it sends as an SMS per normal, and they receive the message.
It seems if this behavior occurs, if I try to send another message within 5 minutes, it still sends as iMessage. After 5 minutes, it seems to work itself out and then sends as an SMS with the green bubble.
The option is NOT available to me to right-click and "Send as SMS" at any point. iMessage treats my initial blue-bubble/iMessage texts to these Android users as legit, with no option to re-send as SMS.
Using Mojave 10.14.5 on a Mid 2014 Retina 15"