Messages on Mac displaying "Not Delivered" but message is being delivered
What are the chances? I just helped someone with this an hour ago. This worked for her.

It appears that the messages database is corrupted. The only fix is to remove all messages. 

From here with edits


Quit out of Messages for Mac
Go to Finder
Hit Command+Shift+G to bring up the “Go To Folder” window
Enter ~/Library/
Move the Messages folder to Trash
Restart the Computer
Open Messages (Nothing should be there) and Test


If it works, great! Otherwise comment back here. 

Note: This will delete all messages from your Mac