My wife and I are having the exact same issues with both of our iPhone 5s and MacBooks. We can send iMessages from our phones but the Messages app on the MacBooks will not sync up or send. As far as I can tell it started around the middle of the day yesterday. We use it all the time so I would have noticed it happening sooner. Very strange because no settings have changed on any device and they are all up to date. I have tried everything mentioned in this thread and still coming up with the same issues where Messages will not sync or send an iMessage to anyone. All contacts are either red and showing not registered with iMessage, even though they are, or it will default to send out a text which works some of the time. However, when I type and send an iMessage on either of our phones, I will see the typing "..." bubble pop up on the Messages app, but the message will never go through. I have had something similar happen before when my wife gets out of data range on her phone but connects to her office wifi and iMessages won't go through. That turned out to be a DNS issue and/or something to do with the Apple ID not being able to verify over her office wifi. A quick reset of the Network settings solved that one, but every time the office wifi changes passwords it screws it all up again even though she can connect.
Here is where I stand:
MacBook Pro Early 2008 - Yosemite 10.10.4
MacBoo Mid 2009 - Yosemite 10.10.4
iPhone 5 (both) - iOS 8.3
•signed out of iCloud everywhere on both the phones and the Macs
•turned off FaceTime and iMessage on both phones
•checked automatic timezone
•checked for duplicated contacts or wrong contact info
•checked both Apple IDs for wrong info
•reset network settings, PRAM, location services, where applicable (the typing "..." bubble on the Macs Messages app reappeared after the location services reset but still did not send all the way...progress I guess)
•removed and added the apple accounts on both Macs and phones
•deleted keychain items associated with iMessage
•deleted that Library>Preferences file, can't remember the full name
•tried adding Apple ID on the phones first before the Macs, and then again with the Macs first then phones
•re-activated text message forwarding with the code that pops up (I have noticed that the text message forwarding option will disappear sometimes, but a network reset brings it back
•tried defaulting to email or phone number and all combinations under send and receive on both mac and phone
•checked DNS servers
•reset modem and router
•disabled/enabled mac messages account, along with a full sign out
Related issue? - On both iPhones if I go to settings>messages>send & receive then click on the apple id>view account it will ask for the password twice then says unable to connect to the iMessage server, but iMessage seems to work just fine. This only happens about 50% of the time. If I try it again 5 minutes later I can view my account details with no problem.
I think that was it. I have tried all of those things multiple times, but nothing worked. This might be worth noting...we occasionally FaceTime with each other during the day and usually have no problems connecting, but the day before we started having iMessage issues FaceTime would not connect completely. I would answer the call, then it would just get stuck on connecting without ever actually going through. Tried calling from both phones, on data, on wifi, and any combo of the two, but would just stay stuck on connecting. I tried it again yesterday after I noticed iMessage wasn't working and it connected to FaceTime just fine. Anyway, it makes me feel a little better I am not the only one experiencing these issues (thought I was going crazy or screwed some setting up), so it kind of eases my mind that I am not missing a step somewhere and the problem is on Apples end. Hopefully it gets fixed soon.