Hi,
Apple Support (or Apple Care) is a paid for service for regular issues after the complimentary period has run out.
(You can of course pay to extend that care).
They will however sort out Apple ID issues for free.
Level 1 people at Apple Support are very script led and hence the "you have to pay" if they don't think it is Hardware or Software related.
If you let them they will run the whole script trying to prove it is one or the other.
Try asking for a Level 2 support person or higher.
These are more likely to take the issue of an Apple ID problem more seriously.
iTunes, FaceTime, Messages, The App Store, Games Centre, Developer access are some of the separate servers that your Apple ID can be used with.
The Serial Number of the Mac is used to create the Auth Token in the Keychain.
It "proves" it is you calling. (It has done so since Messages 7.0.2 at OS X 10.8.2)
Migrating a Keychain from another computer can get the iMessages Server to block your use of the Apple ID when used by your Mac. (i.e. it is App., ID and Server specific depending which way you are looking at it).
The Original issue in OS X 10.8.2 tended to be missing Serial Numbers that were not put back on to Repaired Logic/Motherboards.
After that the server needed resetting.
The problem has occurred during both version 8s in Mavericks and Yosemite but seems to have increased slightly at the OS X 10.11 Upgrade and again at the OS X 10.11.3 update.
That said the Level 2s are still likely to want you to jump though some hoops to prove it is not Hardware or Software related.
Safe Boot, NVRAM resets, testing in another Mac user are among the more common.
Reinstalling to OS, Upgrading the OS if you are using a earlier version or Updating the OS to OS X 10.11.4 are unlikely to change anything.
As I mentioned above they are like to engage with the engineers at some point.
Be polite, persist with it being an Apple ID issue, request that the server is reset regarding your Mac's use of the Apple ID on the iMessages Server.
7:33 pm Sunday; April 17, 2016
iMac 2.5Ghz i5 2011 (El Capitan)
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