Could a regex library parse a regular expression and decide reasonably quickly which engine to use?

Probably, but python-core has no interest in maintaining multiple regular expression implementations: http://mail.python.org/pipermail/python-dev/2010-July/101606... (this thread starts talking about regex, which is a backwards compatible enhancement to re, but also covers re2)

Yes. That's precisely what pyre2 is doing. It's trying re2, and if it fails because it doesn't support the features, it tries the python re. Since compilation happens rarely, this is fast.

Please note that RE2 doesn't support backtracking.

if you're using backtracking, maybe "regular expressions" aren't the right tool.

What would be the right tool, then?

Grammars are a good start. Mix in parse-controlling predicates if that isn't powerful enough (C++).