If you have duplicate keys, why not use a hash of arrays?

Doh!- forgot you wanted them ordered. Still, maybe a tied hash?