That's totally strange also. I thought be able to see and remove devices you have to answer to security questions as well as knowing the password.
In our case, we had a reasonably secure password that hasn't been used for anything other than Microsoft; and the login credentials haven't been used on anything other than the dialogue boxes on the iPhone to sign into the iTunes Store. No phishing attempts. Email address has been secured with two Factor authentication; so no notifications via email would have been able to be deleted.
Admittedly, my computer background is the Java programmer of over 10 years; i've not specialised in security systems, but I'm having real difficult time identifying how this happened to us. Absolutely zero evidence of any activity on the account, or a hack.
I also can't see anything in common with this account, and people also listing that they've been hacked. Different countries, different service providers, different email providers.
The only exception to the above, is that we ordered a new Apple Watch and entered the Apple ID credentials on to the Apple site when ordering Very recently. That's the only place they've been entered really since password last change that wasn't on the iPhone with a black keyboard in iTunes.
You only reason it didn't write up the phone bill was because we have the send as SMS setting switched off. That being said, if they had access to the Apple ID account why didn't they use either of the two credit cards on the account to make any purchases? Or something.
That all this with the fact that iMessage wasn't using the Apple ID at the time, i'm completely utterly clueless as to what has actually happened.
Granted, I can see that with the same sort of Messages are being sent, other people have clearly had the Apple ID compromised in some way, even though they sometimes have new passwords and it seems almost impossible, and they report that after changing the password that the attack can continue or repeat, The advice for us to change our password seems quite strange. We cannot turn on 2FA yet and if this password has been compromised, it was a reasonably secure password, what's to stop them getting the next secure password?
Put it this way, aside from the fact that I hadn't recognised that Apple offered 2 factor authentication until just the other day, we aren't a pair of newbies when it comes to security. We know how to spot a phishing email, broken security, malicious websites; we have 2FA on most accounts. This makes zero sense to me, if Apple has not been compromised / the iPhone itself.
Sorry for the wall of text