(*FAIL) itself doesn't add to regexp complexity and could be exempted from caching

Well it could (if at the top-level of a pattern), but that doesn't solve the issue - there are other regex optimisations (currrent or future) apart from the superlinear cache, any of which could potentially cause a match to "prematurely" fail.

So, is there a way in Perl to find all regexp matches?

I don't know, but I doubt it could be done reliably,

Dave.