I posted some sample code that demonstrates that inserting a key into a hash can change the order of the keys that were present before that insertion. That shows that the keys are inherently unordered. If you us one of the modules out there to hack the inner workings of a hash to control the order of keys you get when calling keys(), it's not a plain hash anymore.
Through the magic of tie and overload and XS, you can subvert and pervert the behavior of things, but that doesn't change the fundamental data types of scalar, hash, and array. Claiming that a hash is ordered is silly, on a par with claiming that pi is actually equal to 3. Being ordered implies a level of stability. If key X comes "before" key Y now, then orderedness implies that no sequence of insertions and deletions that do not invove X or Y will change that. It turned out to be trivial to demonstrate that that condition does not hold.
In reply to Re^4: What makes an array sorted and a hash unsorted?