One thought is a interior cell that belong to the "abroad" faction, and a teleport door somewhere in Cyrodill that leads there. Level 100 lock, belongs to that faction. So they can go there, but the player can't. Needs multiple doors, one for each route "out" but could share holding cell. Door need not be a door, but could be a rock or other static.
Another is to have a script disable the NPC's when they reach an appropriate point near the border, and a timer re-enables them when they're due back. Needs markers at the borders to trigger script on a GetDistance test, so it's probably as much work as the doors above. Plus a script running to monitor it.
Any other ideas?

But if you want the player to be able to run into them on their way to the other province, then yeah, you'll need to place a marker near the border. I'd still disable them when they reach the marker. If they aren't essential, you'll have to make sure they aren't dead when you want to reference them again.