Você pode fazer ações de localizar e substituir bastante complexas com expressões regulares e (por exemplo) o Notepad ++. No entanto, isso pode não ser viável quando o arquivo que você está tentando alterar não tem itens salvos da mesma maneira.
Pessoalmente, como o arquivo é XML, eu simplesmente usaria um ambiente de programação, como o que você está acostumado, para escrever um problema para ler e gravar os arquivos XML. Isso pode ser provavelmente muito mais fácil do que escrever uma expressão regular complexa.
Como alternativa, você poderia usar XML- > XSLT para ler os arquivos e transformá-los, mas eu escolheria a opção com a qual estou mais familiarizado.