Recently, super-smart XML guy Dan Cazzulino blogged about a "bug" that he had found with regexen whereby certain strings would seemingly take forever to match or fail. As I mentioned in the comments, this is certainly not a bug and is purely a result of having written an inefficient regex. This is why it is so important to understand how regexes work on the strings that they match, so that you can know ahead of time if the pattern that you've written will become a backtracking behemoth.
This exact behavior was a major issue for the RegexLib site when I was building it because people could easily submit an inefficient pattern and run it - thereby effectively removing one of the ASP.NET worker threads from the pool. By opening a few windows and running the same inefficient pattern on the site, a would-be attacker could effectively bring the whole RegexLib site down by starving the threadpool.
To counteract this behavior I implemented a special sandbox that allowed me to run all pattern matching in a separate thread that could be timed-out so that no pattern could run for more that a couple of seconds on the site. Of course, given that ASP.NET maintains a limited number of threads to work from you must ensure that, when you do this that you do not kill the thread because once killed it will be unavailable to use again.
I really wish that the CLR team had implemented this sort of behavior out-of-the-box with Regex because writing a cancellable sandbox which runs on another thread is certainly not a trivial exercise. A link to the CancellableWorkItem project which shows how to run work items in a cancellable thread can be found here:
http://projectdistributor.net/Projects/Project.aspx?projectId=121