Slight rant and trying to understand how this works, but in the end I think I agree with Jeebus now.

The -1 card token and Enchatress/Ways replace a thing with something else. That is relatively clean, because now you have something else, the previous thing that was about to happen no longer happens, so other things that would apply to it or try to replace it no longer "work".
Star Chart and Astrologer/Masons do not do this clean replacement IMO, because if they did, you couldn't use both Star Chart and one of those 2 Allies
on the same shuffle. This is a
modifying effect, the "shuffle" isn't replaced with something else, it is modified. For Star Chart, you first select a card and put it somewhere, then do the randomization of the remaining cards (the "shuffle"), then put the selected card on top. But, you can also apply another modifying effect to the randomization, like an Ally. Or you do it in the reverse order, first the Ally, then Star Chart.
For all of this to work as intended, one cannot argue that Star Chart replaces one shuffle with a new, different shuffle. Because if that was the case, you could apply Star Chart again to the new shuffle, and recusively not just topdeck one card, but order the complete deck. While that argument cannot be applied to the Orders alone, I wouldn't want those two to create new shuffles, as this would again allow Star Chart to be applicable to the new shuffle. While this does not really seem to break the game, it seems not good to have those similar effects work in a different way.
All of this means to me, that Star Chart and the 2 Orders are modifying effects, which do not completely replace a shuffle with something else, but they
modify the shuffle, and
other modifying effects can still apply to modified shuffle.
The question is now what should "shuffle" on Emmissary mean? Does it apply to the first "shuffle" it created, or to any modified versions in between, or only to the "final" one? Originally I argued it should apply to the first one it created, but I see that making it "see" the final one only makes sense as well. If that "shuffle" involved 0 cards due to Order of Masons, then it doesn't give the bonus.