The message "Not Delivered" has eluded me longer than it should have after retiring my MacBook Pro 2012 Retina for a 2015 Retina. I was able to message anyone using an iOS device through messages but unable to send SMS to non-iOS phones. Here's the fix, it requires both your iPhone and your Mac to be handy.

Step 1:
Confirm your messages has been configured on your Mac in messages preferences



Step 2:
Go to Settings -> Messages and then finally to Text Message Forwarding



Step 3:
Add your computer:



Step 4:
A confirmation code will be sent to your Mac in Messsages, it may take a few seconds. Be ready to punch in the pin on your iphone.

That's it