Так как вы запросили самый быстрый :
Если (и только если) структура xml всегда согласована: (это псевдокод)
string xml1 = //get xml1 somehow
string xml2 = //get xml2 somehow
xml1 = replace(xml1, "<?xml version=\"1.0\" encoding=\"utf-8\"?>", "");
xml1 = replace(xml1, "<allnodes>", "");
xml1 = replace(xml1, "</allnodes>", "");
xml2 = replace(xml2, "<allnodes>", "<allnodes>\n" + xml1);
Это гигантский хак, но он быстрый. Ожидайте увидеть его на TheDailyWTF, когда ваши коллеги найдут его.