It's not clear to me from p9 of [1]:

"The set of N possible relabelings is reduced to a
more manageable N' consisting of the true labeling
and N-1 randomly chosen from the set of N 1 possible
relabelings."

whether the random selection of a subset should be with-replacement or
without

The intent of the paper was that the random selection was without replacement. However, after writing that, I found that most stats folks don't bother to check if a permutation was run twice when not using all permutations. For example, when Pesarin (2001) recommends a random selection of permutations he does so with replacement; though, to his credit, he's careful to describe this as a "Monte Carlo" method.

Intuitively (but not at all knowledgeably!) I would have
thought that without-replacement would give a better approximation of
the null distribution for a given number of samples. But perhaps not?

I think you'd be hard pressed to see a difference. If the total number of possible permutations is large relative to N', then there should be virtually no chance of using the same permutation twice. And if N isn't much larger than N', you might as well just do all N perms.