Is this at all possible with the way the keys are currently created?

Yes, of course. See the last example of How do I sort an array by (anything)? as a guide.

Would it simply be easier to use a multidimensional hash and then nested loops to try and handle accessing the elements?

Conceivably. However, I think the simplest approach is to extract a single sortable number from each key which you could do like this:

my $index = sprintf("%i.%6.6i", split (/\t/, $key));
[download]

Whether you use this number as the actual key or just use it to sort and then reassemble is up to you.