OK. I tried a few variations, and decided to add some randomization. I also changed the %order key scheme, though probably for the worse:

my %values;
my %order;
my %new_order;
for (1..10) {
  my @l = get_values(20);
  print ">@l\n";
  @values{@l} = ();
  for my $i ( 1 .. $#l ) {
    for my $j ( 0 .. $i-1 ) {
      $order{$l[$j]}{$l[$i]} = -1;
      $order{$l[$i]}{$l[$j]} = 1;
    }
  }
}

my @ordered = sort { $order{$a}{$b} or 0 } keys %values;

print ">>@ordered\n";

exit;

#############

sub get_values
{
  my $k = shift;
  my @list;
  for my $i (1..$k) {
    push @list, $i if (rand > 0.6);
  }
  return @list;
}
[download]

At 0.6, 10 runs, and a length of 20, I get about 50/50 good/bad results. (You could put together a better test case and plots stats for various values of the 3 inputs.)

My data has a very long sequence, hundreds of runs, and a very low threshold. If something is ambiguous, I have to pick a likely sequence anyway. (In some instances there is no single correct sequence, but several that vary in one or two positions...almost like DNA, but that's not what I'm working with.)