This tweaks the implementation rather than the algorithm, which means it comes into the realm of what are usually called micro-optimisations--but it does achieve a near 300% speedup:

#! perl -slw
use strict;
use Time::HiRes qw( gettimeofday tv_interval );

my $maxflips = 0;
my @max_sequence;

for my $num ( 1 .. 10 ) {
    my @start_time = gettimeofday();
    @max_sequence = ();
    print "Pfannkuchen($num) = " . fannkuch( pack 'C*', 1 .. $num ) . 
+" for:";
    print unpack 'C*', $_ for sort @max_sequence;
    my @end_time = gettimeofday();
    print tv_interval ( \@start_time, \@end_time ), " elapsed seconds.
+\n";
}

sub fannkuch {
    my ( $a, $level ) = ( @_, 0 );
    my ( $index, $ok, $copy,  ) = ( $level,  $level + 1 == length( $a 
+), $a );
    do {
        if ($ok) {
            if( ord( $copy ) != 1 
            and ord( substr( $copy, -1 ) ) != length( $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 ) {
                    $maxflips     = $flips;
                    @max_sequence = ();
                }
                push @max_sequence, $copy
                  if ( $maxflips == $flips );
            }
        }
        else {
            fannkuch( $copy, 1 + $level );
        }
        substr( $copy, $index - 1, 2 ) = reverse substr( $copy, $index
+ -1, 2 );

    } while $index--;
    return $maxflips;
}

__END__
P:\test>513179-3
Pfannkuchen(1) = 0 for:
0.000368 elapsed seconds.

Pfannkuchen(2) = 1 for:
21
0.000206 elapsed seconds.

Pfannkuchen(3) = 2 for:
231
312
0.000298 elapsed seconds.

Pfannkuchen(4) = 4 for:
2413
3142
0.000434 elapsed seconds.

Pfannkuchen(5) = 7 for:
31452
0.001012 elapsed seconds.

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

Pfannkuchen(7) = 16 for:
3146752
4762153
0.039062 elapsed seconds.

Pfannkuchen(8) = 22 for:
61578324
0.339917 elapsed seconds.

Pfannkuchen(9) = 30 for:
615972834
3.313848 elapsed seconds.

Pfannkuchen(10) = 38 for:
59186210473
35.109115 elapsed seconds.
[download]

It does limit the algorithm to a maximum of 255 elements (without modifying it to go unicode), but I don't think anyone will be waiting around long enough to notice:)