"some of which are completely incompatible with the usual NFA and DFA algorithms" - It would be nice if you pointed to some article/resource giving more info on this.
Well here's a starter for you. Using enhanced regex syntax you can match a language containing strings of prime length. On the other hand (using the pumping lemma[1]) you can prove that that set is not regular, hence not detectable by a standard regex.
