I'm not sure this is a solution, but it's at least part of the problem. See here:

    foreach my $str (sort {($substrings{$b}[1]-$substrings{$b}[0]) <=>
+ ($substrings{$a}[1]-$substrings{$a}[0]) || $substrings{$a}[0] <=> $s
+ubstrings{$b}[0]} keys %substrings){
[download]

The conditions you give to sort do not differentiate every element. If I go to the end of that block and add "|| warn 'identical item'", this will tell me if there's some pair in the list that the block can't distinguish. Running that, I see that sort encounters such pairs several times. I don't fully understand everything you're doing here, but I would guess that the elements that the condition sees as identical aren't really identical.

So what I think is happening is that on different runs, that sort is sorting differently. I'm not sure why running it once or twice makes a difference, but I suspect it's just perl's internals. For example, maybe keys is giving you the same things in different order, and sort preserves that order.

Anyway, if I add "|| $b cmp $a" in there, it seems to act the way you want. Since you're sorting keys, and they're unique, you can be pretty sure this will offer consistent behavior. The new full line is:

    foreach my $str (sort {($substrings{$b}[1]-$substrings{$b}[0]) <=>
+ ($substrings{$a}[1]-$substrings{$a}[0]) || $substrings{$a}[0] <=> $s
+ubstrings{$b}[0] || $b cmp $a } keys %substrings){
[download]