Following yesterday's StackOverflow outage - is regular expression matching really difficult, or is the implementation simply inefficient?
If you only wanted to parse regular expressions then you wouldn't have such problems (unless you were a really incompetent programmer, I guess). Caveats include the time needed to build an automaton; an asymptotically worse algorithm may outperform the automaton approach in many cases in practice.

The real issue is probably that they use library functions that deal with regexps which are way more powerful than plain regular expressions. Also, features like matching groups introduce further complexity.

In this case, trouble arose because these engines match substrings (with plain regular expressions, we typically only match whole inputs) and use backtracking; long partial matches that eventually mismatch cause long backtracks. In essence, this is the worst-case for naive, quadratic-time string matching.

Can this be improved? Maybe. Using the ideas from string matching automata we would backtrack not to the second symbol, but to the start of the longest suffix that matches a prefix of the pattern. But since the pattern is not fixed anymore, it's certainly not trivial to extend the ideas.