I did some thinking, and decided:
-speed was NOT essential, as this could really be done via a cron job that runs once in a while
-The xml should not change (we've all heard that one!), but we both know that it will
-xml parsing is far more flexible than regex
-regex is far faster in this case
-xml parsing is both cooler, and the Right Thing to do

I will use a parser, I don't know which one, or how to pick it, but since I have experience using java's DOM parser, I'll probably stick with xml::dom