One game that actually did tackle this all the way was Arcanum.
For those who don't remember, what these guys did was make a seeded map generator that filled all those thousand square miles of real-world space between pre-designed locations with something appropriate. And you could literally leave a location, but just keep going without switching to the fast-travel "world map" - and if you went for long enough in the right direction, you'd get somewhere else. But, world size being to scale, you'd literally have to walk hours or days.
Consequently, when in fast travel, if you ran into some randomly generated monsters, the battle map would actually be that exact part of the generated world map. If you happened to run into something else again in the same spot (or close enough), you'd see the same map.
Of course, this made game design somewhat awkward, because if you knew the precise locations of things (they even used latitude/longtitude for map coordinates!), you could just go there right away - unless there was some choke point on the map that you couldn't avoid and that would require direct interaction (like, say, a lone bridge over a river with a bandit collecting toll from any passers-by). And the game was actually designed around that possibility!
The problem with all this is that it's a gargantuan effort to maintain a giant sandbox that most players will just ignore, or possibly never even discover.