You may not want to hear this, but you are just making your life difficult doing this as a regex-- every little permutation in the source HTML is going to potentially break your RE. Why don't you use a module like HTML::TokeParser, which PerlMonks even has this excellent Tutorial about? That way you can run through a pattern of tokens (tags), and when you get into the set of tokens you need, you can run your regex against the text itself without having to worry about all the rest of that stuff.

I find it hard to believe that changing your input alone can cause your script to hang. Unless you have built in some later use of the variables set by this regex, and haven't checked to make sure they actually get set in the cases when the regex fails to match. So maybe is that happening?