To create a bunch of reproducible shuffles, I'd write a shuffle (not particularly hard, you even have example source code for such on CPAN) that uses a Mersenne Twister. The seed space for rand is too small to cover the number of possible shuffles for even a fairly small number of items. A Mersenne Twister supports much larger seeds (and you can find implementations of that on CPAN as well) and so is more likely to be able produce many more of the possible shuffles.

But I'm not convinced that a reproducible shuffle is the best choice for the game scenario you described.