Tes3Mod:World Map

Overview
The world map is the "zoomed out" map that you see in the game map window. It shows the landmasses of the loaded mods, marked locations (yellow squares) and indicates through textures which parts of the map have been visited.

Extent: The game map does not extend indefinitely in all directions, but instead is limited to an area ranging from cell -28,28 (upper left corner) to 27,-27 (lower right corner). While landmasses can be placed outside this area, they will never be drawn on the map. (Caveat: The game engine may try to draw landmasses just to the right and just below this area onto the map. However, the engine does this incorrectly, resulting in land textures that wrap from one side of the map to the other and similar artifacts.)

Updating: Whenever you enter a cell, Morrowind will update the corresponding piece of the world map. Textures for land areas will be applied to the map, but sea areas will be left unchanged. Marker squares are added to the map by reading scrolls, talking to certain NPCs, etc.

If you add a mod that adds a new land area, then Morrowind will update the map for the cells where the mod changes the landscape. However, if you remove or change the mod, then no update will take place -- i.e., the landmass will still show up on the map.

Problems
There are several problems associated with the world map, mainly associated with adding and removing mods.
Lands at the right and lower edge of the visible map may wrap around to the other side of the map or do other odd things.
Landscape associated with mods removed from the loadlist will continue to be shown on the world map. If you visit the area, then the visited area will only partially erase. 
If you use Wrye Mash to add or remove mods, the world map will never be updated.

Wrye Mash now (V 0.54) has a Repair Map function which will update the map as well as add a few tweaks (map border, gridlines). 

Alternatively, there's the brute force solution: delete the world map (FMAP) record from the savegame, or replace it with a correct world map record from another savegame. Several programs can be used to do this, including Enchanted Editor and TESAME. The problem with this approach is that it completely resets the map -- i.e., it causes the map to forget marked and visited cells.

Technical Details
''Note: It's possible that map format may be different for old (pre-Bloodmoon) versions of the game.''
Game map is stored in the FMAP record, which has two subrecords: MAPH and MAPD. 
MAPH is two ints: 512 and 9. 512 is the dimension of the map (512x512) and 9 is the pixel dimension of a cell.
You might hope to change the size of the visible map by editing these, but that doesn't seem to work. I tried changing 9 to 6 and deleting the MAPD. Morrowind just reconstructed the vacant map and set the value back to 9.
MAPD contains the pixel data of the map.
Size is 512x512x3. I.e., it's a 512x512 RGB array. However, the color space appears to be 21 bits, not 24.
The map area is -28,28 to 27,-27. I.e., 56x56 cells. Each cell maps into a 9x9 pixel array. Note that this leaves 8 pixels left over (9pixels x 56 cells = 504 pixels). 
The extra pixels are apparently meant to be used a 4 pixel wide border surrounding the visible cells on all sides. I.e. the first cell (-28,28) doesn't draw at pixel 0,0, but at pixel 4,4.
There's a bug in the Morrowind map updating engine that causes it to try to draw the cells just to the right and below the visible area onto the map. Since the space is not actually available in the pixel map, this results in some minor corruption of the pixel map (e.g., cell area being wrapped around the map).
Terrain is colored according to elevation (land) or depth (sea). Land and sea each seem to have a distinctive color, whose intensity is then scaled to the elevation/depth.
The exception to this is that for sea, the red element is forced to be odd and for land the red element is forced to be even. 
You might think that the odd/even red would be used to distinguish sea from land, and thus the textures to be updated, but actually: 
Textured land can have odd red colors.
The "no overwrite" on update seems to be limited to the shallow sea texture and less intense versions of it. (Even more intense, i.e., whiter versions of the sea shade will be overwritten.)
If you mouse over a visited area, you may still see the name of a cell from a mod that has been removed. This occurs if the cell has been marked with showMap (sets cell flag 32). 
Wrye Mash's repair all function will now (Version 0.55) unmark and unname these cells. Used in conjunction with Mash's Repair Map function, this will remove the cell from the visible map.
Some colors:
Deep Sea: 25,36,33
Shallow Sea: 37,55,50
Low Land: 62,45,31
Marked Cell: 202,165,96