Might be nice if the maps have a "cloud of war" on it at the beginning. You uncover it as you explore the lands.
Makes everyone happy no? No need to buy maps and still provides an incentive to explore.