If the procedural system were only used as inputs for the initial state and the world were based on a chaotic model then the the starting game state (after some iterations of the world model) could be wildly different for very similar sets of input states.
As you mention, the challenge then becomes to define this sort of chaotic system in such a way that the resulting worlds are not 'nonsense'. Nonsense states could be culled using some fitness functions... sounds like fun :-)
Yes, in my mind there are at least two levels of procedural generation:
1) Generating the layout of the world, placement of entities, and other world states (such as available quests or plot devices).
2) The generation of the actual content itself (NPCs, items, terrain, flora, fauna, etc).
Here, I'm mostly referring to the second type. :)
As far as the first type, there is a LOT more you can do with chaotic systems because they are often AI-driven, and AI-driven things can (potentially) have emergent results (although even an AI-less system, like Conway's game of life, can produce many interesting results).
As you mention, the challenge then becomes to define this sort of chaotic system in such a way that the resulting worlds are not 'nonsense'. Nonsense states could be culled using some fitness functions... sounds like fun :-)