... even after the 5.8.1 change to add randomisation.

So, while not yet perfect, the tendency is to randomize the order in which keys or values are returned. keys and values are meant to return their values in no predictable order.

You say,

keys may not return the keys in order, but it could.

Yes, e.g. tying the hash to DB_File, as DB_BTREE. But what's your point? In theory, it could, but in practice, it doesn't. In which theoretical circumstances that would be meaningful in practice, would keys return the keys of a perl untied hash in any meaningful order (i.e. shortest..longest, lexically sorted, lifo/fifo or such) ? And why should it?