I don't think we should have the maps we have taken away, or that new players should have to earn the maps we already have. That would be like trying to put the toothpaste back into the tube.
I do think it would be lame, for example, to infiltrate the Garlean Empire and immediately have the maps available without first doing some sort of reconnaissance quests/missions.

As far as questing maps goes, visiting all the aetheryte camps and nodes might be a good quest objective to get a particular map.