What about just adding a grid to the map? So that the XML would be coded with regions denoted as A1, A2, B1.., ZZ99. Perhaps every single grid wouldn't have a territory, but it would allow clicky maps to be made w/out territory names cluttering the map image.
EDIT
Also, to create maps with regions ...