I have had this happen with two separate iPhones; one a 6s and one a 6s Plus. In the case of the latter, I had the iPhone unlocked five separate times as I worked my way to the engineering team. I was livid, but the A Team finally was engaged. It was nearly a two month process due to my own schedule and coordinating with Apple's tech teams who are off regularly. Ultimately, Apple asked that I send the iPhone for their forensics and they replaced it with a refurbished device. Problem gone.
The second iPhone, the 6s, corroborates some of the theories on this thread, especially the duplicate serial number theory. I never received any info from the forensics report on the 6s Plus, but I did hear them mention Chinese activity of a similarly numbered device.
The 6s was the icing on the cake. It was activation locked on startup, AND, locked to the exact same AppleID as the first iPhone was many months earlier. And here's the kicker...I never logged in with my AppleID with this second device and it had no way of knowing who I was except by cross-referencing my wifi network, which seems completely beyond the pale. It seemed way too wild a coincidence that the exact same AppleID (a Yahoo account) activation locked two of my devices months apart. And let me confirm, I had NEVER seen this AppleID/Yahoo account before the first device.
So what was similar between the two devices? Same Yahoo.com address for activation unlock. Both devices bought on eBay from reputable but novice sellers. No way they knew what they were getting into in terms of facing an unlock process with Apple. Both devices had AppleCare Plus. And both sellers had shared pictures of Apple's AppleCare coverage webpage for the device being sold, including a detail of the device serial number.
My guess is that eBay is a ready supply of intentional and inadvertent serial number publication in listings, though no one would ever record and publish that info if they knew what could happen to it. Furthermore, if you have an IMEI pictured on eBay but no serial number at least one of the lookup services will provide the serial number of the associated device on a free search. So there is a ready stream of Apple Serial Numbers being published on eBay and someone would only need to set up a search script to mail them anytime anyone lists AppleCare or AppleCare Plus in the title in order to be notified of a likely device Serial Number available for deploying. With a lifetime's supply of hacked email accounts (to say nothing of the mega-Yahoo hack), this seems like child's play if the technology exists to write the cloned serial number to another device, which it apparently does.
Based on my experience, I have a couple of recommendations:
1) DON'T attempt to resolve this over the phone with Apple. Bite the bullet and if at all possible, take it to an Apple Store. Provided you have your sales receipt, the genius will see the behavior first hand and will replace the phone.
2) Replacing the iPhone is the only option, in my opinion. I was a masochist to do the unlock five times, and I don't recommend that madness to anyone.
3) Hope is NOT a strategy! It WILL relock. If it's your iPhone, it will be your pain. If you've sold it, it will likely be your pain, as well.
4) If you buy off eBay, avoid devices where IMEI or Serial Number is in the wild. Too easy to skim.
5) If you sell off eBAY, avoid anything which would detail your device info, including actual IMEI or Serial Number.
6) Replace the affected device. Period. It's burnt.
These are my personal recommendations based on my experience and are nothing but my personal opinion. I hope it is helpful to some of you who have or will fall prey to this bummer of an experience. Good luck!