Humm,
That seems interesting.
An iPhone set always implies the Number is the first option.
Namely you enable the app on the iPhone and wait for the Number to verify.
Testing for other would be difficult.
The app would need turning Off.
Then this would need to be done https://selfsolve.apple.com/deregister-imessage
Then the iPhone would need to be isolated from both Carrier and Wifi services when the Messages app was reactivated possibly with the SIM card removed. (essentially make it like a small iPad)
The Mac would be the place I would concentrate on.
The Apple ID has to be an iCloud linked ID but it does not have to be THE iCloud ID.
That is to say in System Preferences > iCloud there is nothing about Messages, iMessages , FaceTime, iBooks, App Store, Game Centre, iTunes and a couple of other places you can login with an Apple ID like the Developers pages.
Therefore you can use different IDs is all of them if you wish. (it makes sense to link iBooks, APp Store and iTunes as the money pot is the same and also iMessages and FaceTime as iMessages chats can invoke FaceTime sessions and people might not accept your call with a different ID).
So, do you use the same Apple ID as you use in iCloud ?
Does the ID work in other places ?
I am presuming the Mac version is one that is saying "error in verification" ?
Since Mountain Lion OS X 10.8.2 (Messages 7.0.2) the app has required the Serial Number of the device is on the Mac.
If you use the Apple Menu top Left and About this Mac can you then click twice on the line that tell you you are running Mavericks ?
The first should reveal the Build number (another way Apple count the OS versions) and the second should reveal the Serial Number.
We don't need to know it but please lets us know f you can see it.
In Yosemite and El Capitan the About this Mac panel has tabs and the Serial Number shows in the Overview tab.
If the Serial Number is missing you will need to take the Mac to an Apple Store and have it put back.
It is sometimes missed if the Logic/Mother board is replaced.
Try a NVRAM reset How to Reset NVRAM on your Mac - Apple Support
Try a Safe Boot
These two provide cleaning of caches that are not done during a normal Restart.
Try setting up iMessages in Messages in A Different Mac User.
See System Preferences > User and Groups (Enable the Guest account or create an "test" Account.)
If this last works then it is setting on your normal account.
If it does not work then it will be that the iMessages server is blocking your ID.
It is a security feature but sometimes it is being triggered when it should not be (and it seems Apple Don't know why either)
The only fix is to have Apple Reset the ID on the iMessages server for your Mac to use it.
(The Serial Number as well as the ID and password make the issue device specific).
Contact Apple support.
Ask to speak to someone higher (level one people are Script led solving Apple Care problems.)
State that it is an Apple ID issue (Free to Fix)
You are still likely to have to jump through hoops regarding data gathering and the like.
You DO NOT need to Update, Upgrade or Reinstall as these change nothing about your User Account settings or anything wrong at the server end.
They may involve the Engineers.
Be polite and insist the reset the server regarding you Mac's use of the the Apple ID.
AS the other devices are using the same ID to sync the iMessages sent to the Apple ID you may have lost the ability to sync if the Apple ID has been logged out for too long.
It is likely that the others may work once the Mac is sorted out.

8:46 pm Friday; April 22, 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),
iPhone and an iPad (2)