If Find My was not activated, therefore there was no Activation Lock, the most likely scenario is that the other person just reset and activated it themselves with this "mysterious" new iCloud account and is lying about it. The device can still be attached to Paul's original Apple account if its not removed from the list of devices by Paul, new activation lock or not.