IMO its a bad habit to use lexicals in such constructs. They will only work once. For instance your code will not work properly if naively converted to a subroutine. The $cnt var needs to be a package scoped var. Otherwise what happens is that the regex is compiled once and the first $cnt will be enclosed into the (?{}), on the second run the new $cnt is not used, rather the original will be used. So for instance

use re 'eval';
sub limited_re {
    my $str=shift;
    my $re=shift;
    my $repl=shift;
    my $times=shift;

    our $cnt;
    local $cnt=0;
    $str =~ s/$re(?(?{++$cnt > $times})\A)/eval $repl/ge;
    print "$str\n";
}

limited_re("111111111",qr/1/,5,2);
limited_re("000000000111111111",qr/1/,2,5);
[download]

Works as expected. Change the our $cnt; local $cnt=0; to a my $cnt; and it won't. I got bitten by this when working on a solution for QOTW 23 (which happens to be on my pad at the time of posting this.)