I can obtain a modest (< 10%) but consistent speedup by modifying the permutation generator so that it doesn't even generate sequences that would fail the extended precheck. Like this:

sub fannkuch {
    my ( $a, $level, $split ) = ( @_, 0, 1 );
    my ( $index, $ok, $copy ) = ( $level, $level + 1 == length( $a ), 
+$a );

    if ($ok) {
        # print "Before munging: ($split) ", unpack('C*', $copy);
        $index = $split - 1;
        substr($copy, $index, 0) = chop($copy);
    }

    do {
        if ($ok) {
            # print "($split) ", unpack('C*', $copy);
            my $q = $copy;
            my ( $k, $flips );
            for ( $flips = 0; ( $k = ord( $q ) ) != 1; $flips++ ) {
                substr( $q, 0, $k ) = reverse substr( $q, 0, $k );
            }
            if ( $flips >= $maxflips ) {
                if ( $flips == $maxflips) {
                    push @max_sequence, $copy;
                }
                else {
                    $maxflips     = $flips;
                    @max_sequence = ($copy);
                }
            }
        }
        else {
            fannkuch( $copy, 1 + $level, $split );
            $split = $level + 1 if $index == $split;
        }
        substr( $copy, $index - 1, 2 ) = reverse substr( $copy, $index
+ -1, 2 );

    } while $index--;
    return $maxflips;
}
[download]

The idea is that $split is the smallest positive number for which all the elements in substr($copy, 0, $split) are less than or equal to $split.

This table shows a few examples:

sequence	$split
15342	1
21345	2
23145	3
23415	4
31425	4
31542	5

(The commented-out debugging statements may make it easier to follow what's going on. They certainly helped me to understand it as I was writing it.)

On each top-level run (i.e. where $ok is true) we can skip directly to the first permutation where the moving element (which starts out as the last one in the list) has passed the split-point.

I've also reordered the maxflips logic, which gives an additional small improvement.

On an unloaded Linux PC, I get the following results. This is the output from diff --side-by-side -W 80, with the output from BrowserUk's code on the left, and mine on the right:

[rpc142: /tmp]$ diff --side-by-side -W 80 fann-char-orig.out fann-char
+.out
Pfannkuchen(1) = 0 for:                 Pfannkuchen(1) = 0 for:
8.7e-05 elapsed seconds.              | 1
                                      > 0.000118 elapsed seconds.

Pfannkuchen(2) = 1 for:                 Pfannkuchen(2) = 1 for:
21                                      21
7.7e-05 elapsed seconds.              | 6.4e-05 elapsed seconds.

Pfannkuchen(3) = 2 for:                 Pfannkuchen(3) = 2 for:
231                                     231
312                                     312
0.000134 elapsed seconds.             | 0.000133 elapsed seconds.

Pfannkuchen(4) = 4 for:                 Pfannkuchen(4) = 4 for:
2413                                    2413
3142                                    3142
0.000307 elapsed seconds.             | 0.000281 elapsed seconds.

Pfannkuchen(5) = 7 for:                 Pfannkuchen(5) = 7 for:
31452                                   31452
0.001292 elapsed seconds.             | 0.001164 elapsed seconds.

Pfannkuchen(6) = 10 for:                Pfannkuchen(6) = 10 for:
365142                                  365142
415263                                  415263
416523                                  416523
456213                                  456213
564132                                  564132
0.008305 elapsed seconds.             | 0.007341 elapsed seconds.

Pfannkuchen(7) = 16 for:                Pfannkuchen(7) = 16 for:
3146752                                 3146752
4762153                                 4762153
0.062369 elapsed seconds.             | 0.056875 elapsed seconds.

Pfannkuchen(8) = 22 for:                Pfannkuchen(8) = 22 for:
61578324                                61578324
0.541676 elapsed seconds.             | 0.498606 elapsed seconds.

Pfannkuchen(9) = 30 for:                Pfannkuchen(9) = 30 for:
615972834                               615972834
5.347029 elapsed seconds.             | 4.943895 elapsed seconds.

Pfannkuchen(10) = 38 for:               Pfannkuchen(10) = 38 for:
59186210473                             59186210473
58.118665 elapsed seconds.            | 54.24672 elapsed seconds.
[download]