Jay Wilson stated in an interview that dungeons will be randomly generated - in true Diablo tradition. Btw, Jay is Diablo 3 lead designer.
Outdoors will be persistent, however, and will not change from game to game. In other words, you can use landmarks in multiplayer as meeting places. I.e. Meet me by the river ford.
CG: Are the dungeons still going to be randomly generated?
JW: All the dungeons’ layouts are randomly generated. The exteriors are not. We have a new system of adventures that allows us to cut sections out of the terrain to put random — whatever — in there. We can put random terrain, we can put in scripted events — we wanted to add a lot more scripted events into the game.
So expect that outdoor monsters could be heavily scripted (as the terrain stays constant). They could run to a chest, get a bigger axe and come back.
The other thing I’d like to see in Diablo 3 is getting better, bigger “rogue camps”. Come on, Jay, you can make a city that’s more than 3 houses. Let’s hope that Caldium (picture right) is that city.