And yet, it seems very unlikely that effectively changing the hash function would result in identical output order. The output order is based on the hashed key values modulo the number of buckets, so changing the hash function is very likely to change the output order.

So test the effectiveness of the randomization directly: See which hash keys collide. If the same hash keys collide between runs, then the randomization isn't doing what it is supposed to:

my %hash;
my $key= 'aa';
my $count= @ARGV ? shift(@ARGV) : 20;
$hash{$key}= 'base';
while( 1 ) {
    $hash{++$key}= 'test';
    if( %hash =~ /^1/ ) {
        print "Collision: $key\n";
        exit   if  --$count <= 0;
    }
    delete $hash{$key};
}
[download]

I always get the same output, but this PERL_HASH_SEED_DEBUG environment variable doesn't work for me so I won't jump to any conclusions (my 5.008_007 is new enough that it should include it, however).