Claro, no uses un XML, no es lo adecuado para eso, lo mejor para tal caso es usar una base de datos.
En el caso de que sea forzoso entonces usa cache, copia todo el contenido del XML y pasalo a un arreglo, guarda ese arreglo en forma serializada en otro archivo, eso le toma menos tiempo a PHP procesar y solo monitorea con
filemtime() cada que cambie el archivo y re-generas el cache.
Puedes ver
Zend_Cache para abstraer ese proceso.
Saludos
