When you reference a web service you don't need to parse the XML, the objects will be created for you through the generated proxy/client class.
You will then have a .NET object that you can modify the values of.
If you want, you can then save it out as XML using XmlSerializer
]. This is a good doc with lots of explanation and good examples.
With the object in hand, you can then just do property assignment instead of search and replace.
There really should be any need to parse/edit the XML directly (unless there's a requirement here you've not yet listed). SOAP isn't meant to be something used by humans.