The more I think about it the more impossible it seems that there could be ANY story in this game. Even if they managed to procedurally generate one planet + missions, the next generated planet would have to 'make sense' and fit into the story (if it's close by, then has it been taken over by the nearby planetary race? If they are a warrior race then do they use the planet as an outpost, with bases strategically placed around the planet? What does the planet add to the story mission-wise?)
And after all that, the 3rd generated planet would need to take into account the story of the other other 2 planets and so on and so on.. (even if the planets don't interact, the missions still need variety)
I agree with your scripting idea, to extend upon it: they release the game with an editor, then a designer would go in and use the editor to pre-generate a set of planets to their liking, and then they could layer story, missions, characters etc on top. Sort of like a build your own Mass Effect.
There could even be wormholes joining all the player created universes together! Oh the possibilities...