Gavin,
Tie::IxHash preserves the order the keys were entered into the hash and has some rudimentary sorting capabilities. I am not sure I quite understand your problem but it sounds like you want to have the order of one hash be dependent on what's in another hash.

Typically, you would would just roll your own sort routine but it sounds like you want to automagically have the hash come out in the order you want regardless of when and how you modify the hash. At the cost of a little performance and memory, you can use my module Tie::Hash::Sorted to accomplish this.

Check out the example sort routine. It determines the order of one hash by the value of another hash. If you have a hard time using the module to accomplish what you want, let me know and I will attempt to help further.