Given my interpretation of `perldoc -f keys`, and `perldoc perlrun`, every time I call keys() on a hash, even between runs of perl, I will get a different order.

No. The order of the items returned by keys, values and each for a given hash is the same for all three function, and the order doesn't change as long as the hash doesn't change.

The order may change between runs, and the order may change if the contents of the hash changes.

So your question remains. I don't know the answer, but I think what's random is the max bucket size. If so, you may not see a difference with just a few items.