welchavw,
To my knowledge, no module exists that maintains sort order of a HoH at all levels. One way to do it would be to tie each hash seperately using Tie::IxHash or Tie::Hash::Array, then construct your final tied HoH. They probably has the functionality you are looking for, but it will be a pain to tie all levels.

I don't know if you can overload keys, but that might be the way to go.

<plug>
If your needs change, and you are looking for something more robust in maintaining sorted order, you can look for Tie::Hash::Sorted when it is released in the next few days. In the interim, you can read about it here and here.
</plug>

Cheers - L~R