Anecdote time.
On Wednesday September 21st, in the afternoon I could no longer send nor receive iMessages on my iPhone 5S. Upon rebooting I got the activation lock screen. At the same time I got an email from Apple (which I couldn't see at the time) that "'iPhone Name' was automatically removed as a trusted device from two-step verification for your Apple ID (xxxx@xxxx.xxx)." Fortunately, that email address was my own, and after re-authenticating I got another email from Apple saying "The following information for your Apple ID (xxxx@xxxx.xxx) was updated on September 21, 2016. Trusted Device Added - iPhone Name."
I spent that evening going through my Apple ID as thoroughly as possible, making sure all info and settings were legit. My initial fear was that somebody hijacked my Apple ID, but that didn't seem to be the case.
No backup or restore or reset was at all involved in the above situation.
My personal experience, plus the reports here, leads me to believe Apple is having some difficulty with the relationships between devices and Apple IDs. Which is odd, because I thought this was something stored on the phone, not Apple's servers. If it's something controlled by Apple's servers, that means it's subject to exploits by an entity posing as Apple.