If your proceduralism doesn't generate easy to hard solvable problems (ie from geometry constraints etc), its not really adding to the gameplay, only the visual experience.

I'm thinking of the generated history and legends too - NMS only seems to gesture at this with wrecks of ships but I don't think it actually gives each planet a history.