Hi,
As far was we can tell from the Posts and what some people report when they post back we think this is at Apple's end.
AT OS X 10.8.2 there was an update to Messages 7 to make it version 7.0.1
Many people at that time who found they did not have their Serial Number on their Computer (repairs and refurbishments involving the logic/Mother board) found they could not login and got a large Pop error message.
We also know that an Auth token was created in the Keychain and it seems that not only does a login use a Apple ID and Password or an iPhone Number but a Serial Number as well.
This means a login can be pinned down to a specific machine.
From there it seems there is an over zealous security feature or a bug that trips this from some Macs.
Once this has tripped then only Apple can reset it.
At Messages 7.0.1 when it only involved missing Serial Number that had been replaced it seems the Level 2 people could reset it at once.
Variations of not being able to Login (Contacts going red and "Not Registered with iMessages" and Sent items getting marked "Not Delivered") have persisted through Mavericks and Yosemite and just upgrading to El Capitan has done it for some.
The fact it gets bumped to the engineers who now seem to be the only ones able to reset invariably involves lots of testing and data grabbing judging from some of the posts.
This seems to indicate Apple don't know what triggers it.
7:42 pm Sunday; March 6, 2016
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