Wonder how it would work for carriages then...
Would the owner of the carriage say "Sorry, can't take you there right now. I know where it is, but you haven't discovered it yet, so I can't take you there!"?
Hopefully they'll just be fairly expensive so you'd at least have to earn some money before you'd be able to use them to get places.
Personally I hope unknown places on the map are fogged over until you get there, like Morrowind. Being able to see the whole map, all the cities and all the roads leading to them right in the beginning of Oblivion kind of ruined the exploration a bit.