Just ran across a Mark-Jason Dominus article on writing your own regex engine. Reading the article and just contemplating writing the code is enough to give you insight into how regex engines work. And the more you know about regex engines the less often you'll be surprised by their behavior =)

For non-Perl users, it's worth checking out the Perl community's regex knowledge base. They've got a long history of regex use and struggle (and everyone seems to have copied their regex implementation). Mark-Jason's writings are one good place to start. His regex talk is one of the best. The talk's not free, but he's been nice enough to put the slides up.