I thought I had already written this, weird...

Working along moritz' suggestions of using larger regexes, in combination with some additional pre-processing and an upgrade to v.10.0, I am now down to 2.5 minutes on my local machine. Thus I am happy, and you do not need to post any more in this thread for the sake of helping me out.

Thanks all of you who wrote here.