Well, as of 1.4.7 I think, when making a map and opening it for the first time, the map is completely loaded, without having to explore anything. However, there was an "unexplored" part on the map. (Superflat "redstone ready" prefix was used)
The same bug happens when making the map bigger (As in, placing paper around the map in the crafting table).