If you're specifically referring to "Since Perl 5.8.1 the ordering is different even between different runs of Perl...", I think the "different runs of Perl" is meant to be taken literally, i.e. executing the perl binary. I.e. when dumping the HASH_SEED value, you should in fact get different values each time (unless perl has been built with -DUSE_HASH_SEED_EXPLICIT — see perlrun):

$ PERL_HASH_SEED_DEBUG=1 perl -e1
HASH_SEED = 12018612040932336001 

$ PERL_HASH_SEED_DEBUG=1 perl -e1
HASH_SEED = 4459772231957961225

...
[download]

That being said, I still always do get the same ordering every time I do keys %hash ...   So, I'd be interested in an explanation just as much you seem to be :)

Update:  here's some test code:

#!/usr/bin/perl

use Test::More;
plan tests => 1;

my %hash = (
    "Zero","0","One","1","Two","2", "Three", "3",
    "Four", "4", "Five", "5", "Six", "6",
);

print "$ENV{PERL_INVOCATION_COUNT}: ";

# note: test string has been determined experimentally
# (i.e. it might differ with your Perl)
ok(join(' ', keys %hash) eq 'Five Four Three Zero Two Six One', q{same
+ ordering});

if (++$ENV{PERL_INVOCATION_COUNT} < 100 ) {
    exec $0;
}
[download]

(prints 100 times "ok ..." with my Perl — despite different hash seed values)