(The comment is supposed to be an addition, not argumentative)
Whilst certainly a good idea, it only works within a specific rules framework, so while its procedurally generated you still need a certain amount of control over the result, atleast to provide the player with an adequete result, as certain factors need to be fixed, I believe this method was used for diablo where naturally certain mission specific enemies needed inclusion.
As for the generation of enviroments Fractals can be considered a general purpose approch, which varies in its success dependant upon the skill of the implementer, and the particular techniques used.
What can be said is that a good system for generating large procedural enviroments can initially take longer than content generation, but its general purpose reuseablity makes the investment worth while in the long run.
An example of this, take a terrain, a good 3D artist can generate a heightmap and manipulate it extremely quickly in a 3D modelling program, where a programmer would be forced to generate the code which makes the mesh, and then write algorithms to generate a heightmap, this takes alot longer than the 3D artist every would. While the 3D artist has direct control of the single result. The algorithm will produce potentially infinate results, some may be deemed inappropriate.
I suppose the best results yielded by such a method would be one which combines the ability to have a bit of both. I personally from results of systems I've experimented with find that so long as the scope is large enough, randomly generated terrains can be really cheap in terms of memory, and provide good results.
Most naturally occuring objects can be procedurally generated.
edit: I often argue that procedural content will finally get rid of designers, and artists, now all programmers need to do is figure out a way to dispose of management. LOL j/k.