They've got someone who works in Apple or at least has access to their service system so maybe an authorised reseller etc.

There's supposedly a form that can be filled in for when people have sold on a device with iCloud lock active, and via the internal systems they can unlock them.

If the details flag as stolen the device is a paperweight though without resorting to chip rewrites as mentioned above.