EDIT: I should have made it clear that ordering is important and that 'this guy' is a simple man and can only love one thing. I know that this hints that I should be using an array of arrays instead of a hash of arrays, but the key-value relationship is something I would like to preserve if at all possible.
After reading your EDIT, I am confused as to what the requirements really are. What does "ordering is important" mean? Order of "what" exactly?
A hash has no intrinsic "order" to the keys - you should assume that hash keys will come out in any order when you access a hash via (keys %hash) or (keys %$ref_2_hash).
It would help at least me, if you could back up a bit.. Write some more text describing what data you have and the kind of "look-up" that you desire. It could be that excellent solutions are being offered to the "wrong problem".