no idea if this is best practice or not: in our HR system the employee retains their employee ID. So we update the old record's external ID to be 12345_oldsub and create a new record with external ID 12345 in the correct subsidiary.
If they move back, we update 12345 to 12345_tempsub and update 12345_oldsub to 12345
It's kind of confusing to write down so hope that offers some kind of insight