I'm not familiar with Stronghold Kingdoms. However, I have done some work with a grand strategy game of my own (though this project, like a lot of my projects, got shelved a while back). Lets talk, instead, about how the kings of grand strategy, Paradox Development Studios do their maps;
First, Paradox seems to have a large number of files that build up their maps. The main one we want to talk about here is the province map, which details what provinces there are and what territory they actually contain. In this file, all provinces have a unique colour. What colour each pixel is indicates which province is where. However, a pixel in this map does not necessarily correspond to a pixel in game, and likely will be multiple in game pixels to a map file pixel.
Next, there is the definitions file, which is a csv file containing the province id, red, green, blue. This links the various province data files to the territory given in the province map.
Each province has its own file, which details the various resources, religion, culture, history and so on.
Then, there are various other maps, which match the other map, but detail other things. For example, a map of all the rivers, a heightmap, a terrain map and so on. For each of these world map images, a pixel maps to the same pixel on another map (I believe). So, rather than try to contain all the data in one file, its contained in several and then used to build things up.
In the game itself, the map is generated at game load (and cached, as this can take some time). As Paradox games are 3d, the heightmap is used to make the heights, then the provinces are overlaid over this. I'm not sure of the technical details.
The Province map is also used to calculate which provinces are next to each other. When I tried my hand at making a Grand Strategy game, the method I used was to iterate through each pixel on each row, and when it changed colour, add this to a list of adjacencies. Then do the same for columns. This can take a while, however, so caching is important to keep load times down.
There is more to it than that, but that's the basics.