> use a regex engine with runtime guarantees

That's a good idea.

If you have to use one that supports NP-hard features I think a configurable CPU time timeout is also a reasonable backstop, just as configurable timeouts are reasonable in network code.