Do you need to activate an iPhone 5s with the original carrier sim card before you can factory unlock it?
No. A factory unlock feeds the unlock status to the collective database that iTunes or the device polls when it does the activation.

Once the carrier has confirmed unlock status (or Apple feeds the unlock status to the carriers when you buy an iPhone factory unlocked out of the box) - the next restore event will alert you that the device is now unlocked.

In the case of a third party unlock - again, as long as the device sees that it is whitelisted when activation time happens, it doesn't matter who caused your phone's device ID to be cleared - just that it matches perfectly for the unlock to succeed.