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.
Confirm your messages has been configured on your Mac in messages preferences
Go to Settings -> Messages and then finally to Text Message Forwarding
Add your computer:
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.