I'm not even going to pretend having knowledge of the regex engine, but I'm happy to do the gruntwork :-)

Confirmed on Debian Etch amd64 with a built-from-source perl 5.10.0:

rhesa@apollo64:~/devel/test/pm$ perl -s 669148 -S=1e6 -N=13104 | wc -l
Trying 13104 probes with perl 5.010000 at 669148 line 18.
1203554358 at 669148 line 20.
1203554362 at 669148 line 27.
11376

rhesa@apollo64:~/devel/test/pm$ perl -s 669148 -S=1e6 -N=13105 | wc -l
Trying 13105 probes with perl 5.010000 at 669148 line 18.
1203554370 at 669148 line 20.
^C after about 500 seconds
[download]

And on a 32 bits build under CentOS 4.x:

[rhesa@mp-cent-07 tmp]$ /opt/perl5.10/bin/perl -s 669148 -S=1e6 -N=131
+04 | wc -l
Trying 13104 probes with perl 5.010000 at 669148 line 18.
1203554602 at 669148 line 20.
1203554606 at 669148 line 27.
11376

[rhesa@mp-cent-07 tmp]$ /opt/perl5.10/bin/perl -s 669148 -S=1e6 -N=131
+05 | wc -l
Trying 13105 probes with perl 5.010000 at 669148 line 18.
1203554645 at 669148 line 20.
^C after about 400 seconds
[download]