Hi,
Lets be clear.
Since this thread started there have been about 6 different types of error, some with error messages that have been seen over the life of Messages in Mountain Lion and Mavericks.
The first 4 are covered in this Doc FaceTime, Game Center, Messages: Troubleshooting sign in issues
Then there is the Serial Number issue that is not documented anywhere and started at the OS X 10.8.2 update and for some may have started with a Mavericks Install. This one can only be "fixed" by a visit to an Apple Store or Apple Authorised Service Provider (AASP).
Next we have the Error message that is shown that looks like this
Obviously it lists your Apple ID and gives you and individual Customer Code.
It too can only be "fixed" by contacting Apple Support. Since it was first seen in Mountain Lion/Messages 7 it has featured less to the extent some Support Staff don't know about it and try to say you have a Hardware or Software issue and try and charge you for an Out of Warranty payment.
It is actually and Account issue that only effects the Mac and the iMessages server. Ask to speak to the Level 2 person if you have no luck.
Then there is an issue where the App will not launch properly.
This is caused by the AppleGothic.ttf Font being either Off or damaged.
It is required by the Messages app to login and Register the Apple ID for the iMessages account. (it appears this is done each App Launch).
Currently the Font is held in Hard Drive Name/Library/Fonts. Required Fonts are normally held in Hard Drive Name/System/Library/Fonts.
Fixes reported have included moving the font to the System/Library/Font location. Another is to use the Finder to Duplicate the Font and then move the Original and Rename the Duplicate which seems to reactivate the font.
Checking it Validates and is On with the Font Book App is useful.
There is a issue that has changed in recent times.
You iMessages account appears to Login. However when you try to send an iMessages it turns the Contacts name Red and says they are not iMessages registered (And All Contacts show this way).
It have been seen that a Fresh Install (Erase Drive and reinstall and don't migrate anything back) and starting Messages does not cure this.
The only things not changed are the Serial Number and the Apple ID itself along with it's login to the iMessage server.
This has been reported to Feedback http://www.apple.com/feedback/ and the more that do so the better. It has also been reported to the Hosts to pass it on and Level 6 Posters can report such things in the Lounge.
There is a New error message I have only seen posted twice.
It relates to the Device "Not having the right Credentials". These might be Yosemite Beta messages but that cannot be discussed here.
It would suggest that Apple are working on something around the issues effecting apparent Login but no Messages Sending however that appears symptom-wise.
Realistically it still looks like an Account problem and I would suggest contacting Apple Support and getting them to Check the account at iMessages as there are other known issues.
All of the fixes listed so far in this thread have worked with at least one of the issues.
There is no one coverall Fix at the moment.
8:05 pm Sunday; October 5, 2014
iMac 2.5Ghz i5 2011 (Mavericks 10.9)
G4/1GhzDual MDD (Leopard 10.5.8)
MacBookPro 2Gb (Snow Leopard 10.6.8)
Mac OS X (10.6.8),
Couple of iPhones and an iPad