Regular expressions will exhibit the same behavior. They will also short circuit if no match is possible/ In essence the behavior that causes the problem is a desirable performance optimization for the general case that you just need to prevent here.

I seriously doubt regex with grouping, greediness and repetition exhibit the temporal properties of purely linear character-by-character matches...

Doesn't have to exhibit "the temporal properties of purely linear character-by-character matches" and noone said that strawman.

It just has to exhibit the "correct matching strings return faster" property, whatever more complicated search it does.

Doesn't it have to exhibit "correctly matching strings return faster ... on a per-character or other tiny chunk basis" in order to work the match towards correctness?

Yes, and it will indeed try by all means to exhibit that behavior -- unless if it's some contrived regex designed to counter this.

The key word here is "short cirtuit" the match, and any regex engine worth its salt will try to do that as much as possible, tranforming the regex to the faster FSM it can.