This isn't a bug, it's intended behaviour :-). The superlinear cache kicks in for various types of complex/nested quantifiers (such as
(z?)+) to avoid heat-death-of-the-universe time to find failure. It records pattern/string position combos where a match failed, and if it comes across the same combo again it stops and backtracks immediately at that point rather than continuing with the rest of the pattern (which will inevitably fail later).
See the very first paragraph in perlre.pod about re_evals:
B<WARNING>: Using this feature safely requires that you understand its
limitations. Code executed that has side effects may not perform identically
from version to version due to the effect of future optimisations in the regex
engine. For more information on this, see L</Embedded Code Execution
Frequency>
Where that link goes to:
Embedded Code Execution Frequency
Dave.