Let's all look a few years back to FFXII. I personally think the way that the map was handled on that game was near perfect. You explore and it would fill in as you explore. You can buy the map, and it outlines the rest of the area, but the unexplored areas are still slightly darkened, and are brighter once you have explored them.

The only thing different since this is a MMO, would be to possibly have some of the out of the way, higher level areas, with end game content, maybe have a small quest to obtain the map. Of course, if you didn't want to do the quest, you could just fill in the map yourself.