Bueno este problema lo puedes resolver de una manera mas fácil si usas una base de datos. Incluso puede ser una pequeña base de datos como sqlite3.
Ahora, si quieres hacerlo con xml puedes hacerlo de la siguiente manera:
- Abre tu archivo .xml
- Cargalo a memoria usando un parser xml. (Tu estas usando el minidom de python pero puede usar lxml o BeautifulSoup
- Haz los cambios que necesites hacer en memoria.
- Al final escribe los cambios en el archivo.