I've tried every suggestion I could find on Apple forums. Deleted .plist files, removed message caches, reset passwords, coordinated sign on/offs between my iPhone and my Macs, reset iPhone and reinstalled Mavericks on my Macbook Air. All pointless exercises.
I suspect it all started because I jailbroke my iPhone using Pangu. It may or may not have been the culprit, but my problems started a couple of days after I did it. All my phone conversations went green and stopped synchronizing with Messages apps on my Macs. Trying to send a new message from Macs would result in either "Your message could not be sent" error with a warning icon next to it, or:
XXX is not registered with iMessage.
So I restored my iPhone to factory defaults using iTunes. That didn't help immediately, but in a day or two, my conversations with other iPhone users went blue. So I am happy that works.
So now I sacrificed my Macbook Air to try and make messages work on it. I reinstalled Mavericks several times, each time trying different approaches: not immediately signing into iCloud, not associating an iCloud profile with login profile, etc. Nothing helps. I launch Messages app, it asks me to sign in (and I do, successfully), and then nothing goes through.
Sending messages to myself also works inconsistently. Yesterday, whatever I sent to myself (using phone number) would appear delivered to the same window, but not on my phone. Today I get "... not registered with iMessage" error.