In particular, counted repetitions ({n,m}) have to be expanded when
figuring the 'N' of the size of the regexp, while back-references
(\digit) are, IIRC, worst-case exponential to match.

That's because back-references leave the class of regular languages,
but I am surprised right now that the manual does not say so.
This egrep expression shows that is an entertaining way:
^(aa+)\1+$
It does not match if the length of the string of a characters is prime,
because the group is a prime factor. A DFA can not do that, because it
contains only a finite number of states, thus being unable to compute
with natural numbers. I guess I should think less about regular
expressions. :)
Michael