Is it the implementations, or is it regexes themselves? I was under the impression that SNOBOL/SPITBOL/REBOL was the gold standard... But I guess you're saying that given some (posix?) regex syntax, implementations can/should be improved? (while eg REBOL/Red-lang goes more towards "a more pragmatic regular language for pattern recognition", I guess ?)
Rebol and Red use embedded PEG parsers, which, by definition, support context-free, and not just regular, languages.
That would be a stretch goal for me: build a regular expression / automata library that's sufficiently modular to keep some components and drop in more expressive constructs (not necessarily PEGs, but maybe pushdown automata).
http://nim-lang.github.io/Nim/pegs.html
> Simple PEG (Parsing expression grammar) matching. Uses no memorization, but uses superoperators and symbol inlining to improve performance. Note: Matching performance is hopefully competitive with optimized regular expression engines.