I was having the same issue, here is what it took to fix it:
Deregister all iPhones from your Apple ID(s)
Put your sim card into an iPhone and turn off iMessages
If you use a Mac, open the Messages App and deactivate your Apple ID(s)
Go to iCloud and tell it to erase all of your iPhones for all...