UPDATE: Also see my follow-up post on an alternative method for replacing nodes.
Joe Gregorio asks about available XML diff formats, and based on some Googling, there really isn't anything robust and/or readable out there.
In particular, most formats seem to hard code differences by node number, which doesn't hold up at all well if you may want to merge diffs from multiple sources from a single code base a la traditional diff merging in code bases.
Given the enormous amounts of XML being processed, it seems incredible that nothing has been defined no standards have emerged so far. So here's a possible option. It's based heavily on the Mozilla XUL Overlays pattern, but generalised for any XML.