AK108:

Unfortunately, this method removes randomness from then on, which isn't acceptable. Reseeding is a possibility, but ugly. I have things later on that I want to be really random.

You can have both a stable shuffle and your randomness requirement by using two random number generators. Use one for the shuffle, reseeding to recreate the original shuffle. Use the other for all your other random needs...

...roboticus