There are exactly two reasons that regular expression parsing "needs" to be slow. First, we have the "ad hoc extensions for doing this inefficiently and in a limited fashion", and second, we have subexpression capture. Backreferences (the former) are generally only useful in situations where you really ought to be using some other construct. The backreferences are the part that's NP-complete.
Subexpression capture is great, and at least that can be done in (low-order) polynomial time with a nondeterministic automaton approach. So really, the only problem is the backreferences.
Using regular expressions to break the input text into tokens ("tokenizing" or "lexing") and then matching the sequence of tokens according to a grammar ("parsing") is usually much simpler. The two-phase approach often factors out some complexity - only the lexer needs to care about things like whitespace, for example.
While most compiler textbooks cover lexing and parsing, I particularly recommend Andrew Appel's _Modern Compiler Implementation in ML_ and Niklaus Wirth's _Compiler Construction_ (free online, http://www-old.oberon.ethz.ch/WirthPubl/CBEAll.pdf).
More recommendations on learning parsing here: http://news.ycombinator.com/item?id=1820858