I was explaining the principle of KISS to my son this past weekend. Sometimes stepping back from the monitor and thinking around the white board is all it takes to come up with simple solutions.
For all practical purposes xml file is nothing but text file. So, you problem can easily be simplified as working between two text files, irrespective of text file, xml file, source code file etc. The xml file only comes to issue once your start consuming it as xml, but in the case of search/replace it is nothing but text file. The only thing you need to keep in mind is not to break your xml tags.
Think it this way, I can open xml file in my favorite text editor and do some search/replace and save the file. How is that different from what you trying to achieve.
So, if we agree so far, it can easily be through may ways, perhaps regular expression might be good candidate for such task.
Here as some helpers
How to: Search Strings Using Regular Expressions (C# Programming Guide)http://msdn.microsoft.com/en-us/library/ms228595(v=vs.80).aspx[
^]
C# Demo Application Illustrating the Use of Regular Expressions with The .NET Frameworkhttp://www.regular-expressions.info/dotnetexample.html[
^]