Venerable monks, someone just told me that their perl (v5.8.1-RC3/darwin) stored hashes differently between different invocations of a program.

Yes, this is to avoid denial of service attacks based on deliberately feeding a Perl pathological data.

Does anybody know if there's a random generator in the hash algorithm of some perl implementations?

Yes, people who compulsively read the the release notes. :-)