I don't see a major problem with randomly generated encounter areas... really, the only difference between that and the original Fallouts would be that there would actually be some variety to the encounters rather than having them play out on the same four or five endlessly circulated maps.
If you made each "key area" a respectable size and gave them large outskirts areas that were pre-desisnged, and then added in a map screen for overworld travel with randomly generated encounter maps, you could have the best of both worlds-- a meticulously planned and plotted game with plenty of interesting storyline quests and detailed exploration and a total "pre-determined" map area equal in size to New Vegas or even F3, as well as a game with realistic overland distances, plenty of faffing about and killing random life forms (if you're into that) and a total gameworld size equal to that of the original games. You could even bring back the luck-based (or perhaps now, luck-, survival-, and/or perception-based) special random encounters from F1 and 2.