It sounds like you've already considered and discarded this, but I'll suggest it anyway: IxHash.

But a couple of other options that you didn't mention are:

1. A normal associative array; that is, two parallel arrays manually kept in sync. It means you'd have to grep or foreach over the list to find your element, but you'd preserve order by pushing entries onto your worklist.
   
   
2. A pseudo-hash. Everyone seems to hate them, and they won't be around in Perl 6, but they seem to do what you want. Basically, you'd do your key lookup in the first element of the array, which is a hash, and then use the returned array index to pull out the appropriate entry. You would likewise push elements onto the array to preserve order, but at the same time add the new entry to the hash.
   
   

   my $pseudo_hash = [ { a => 1, b => 2, c => 3 }, 'A', 'B', 'C' ];
   print $pseudo_hash->{b}; # prints 'B'
   print $pseudo_hash->[2]; # prints 'B'
   print $pseudo_hash->[$pseudo_hash->[0]->{b}]; # prints 'B'
   [download]

Update: at jdporter's suggestion above, I installed and took a look at IxHash. Interestingly, it's implemented as a synthesis of a pseudo-hash and an associative array. The first element of the array is the hash for key/index mappings, and the two subsequent entries in the array are arrays for the keys and data themselves.