This problem has been seen on mid-2012 MacBook Pros on Mavericks and on late-2014 Retina MacBook Pros on Yosemite.
One day while using iMessage on the Mac, all the contacts turned red and messages failed to send, immediately returning a "not delivered" error. It also reported when trying to resend the messages that the contacts were no longer associated with an iMessage account.
Things that didn't fix this behavior:
Removing the Apple ID information from my phone, turning off iMessage on both of the devices, and placing my iPhone in airplane mode for several minutes before turning it on logging in again.
Could someone help me figure out how to solve this?