One approach to redefining sort order is to not use the sort function explicitly, but instead to tie the hash up front so that keys are maintained in a specific order and the contract with the rest of the code is to just use the keys function to get the right order. A lot of extra overhead maybe, but something to consider.

Approach #2, which I have used to a degree, is to object-ify any hashes of this nature (or this sort even 8-) and have each provide it's own sort method. Since object overhead is relatively low in Perl this one usually works out fairly well in my experience. Still a lot of extra work if it's for localized use.

Whenver I see a suggestion to change a base language characteristic my mind sends out a "wrapper" alert.