Personally, I have a general method for choosing XML modules to use. Thus, one way is to go through the XHTML, and build up a new XML::Twig object holding the new info, then to dump that.

However, if all you're doing is Transforming from XML (which XHTML is) to something else, especially something else that is XML-like (in this case, actual XML), then that sounds like exactly what XSLT is for. I suppose that if you have to do some magic parsing of some nodes to split out information from the text rather than build it up, it may get more painful, and that's where the perl w/XML::Twig comes in.