The answer is that we don't avoid it, but we try to mitigate it.
Procedural technology is driven by algorithms and seed-values (which are used to initialise the algorithm with). Virtually always (and it is certainly what you want) you have no randomness in a procedural system, so if you run your algorithm several times using the same seed you would come up with the same result. One seed = one result.
Your first problem is therefore to ensure that you have a sufficient nr of seed-values available and here scale can become something of a problem. You asked about the galaxy so let us use that as an example. The real galaxy has something like 200 - 400 billion stars in it. It is unclear how many planets there are, but games - because they are games and therefore have the purpose of being fun - would normally want to ensure that planets were reasonably common. Given that, let us say that a representation of our galaxy would contain 1 trillion planets (**). So somewhere you would have to store that number of seeds (or be able to calculate the seed when you needed it). And you must ensure that it is unique for each planet.
Your next problem is that while one seed = one result it doesn't mean that four different seeds = four different results and it is here that the algorithm comes into play. As a simple example, remember the sine-function? sine(0) = 0, sine(90) = 1, sine(180) = 0, sine(270) = -1. (this is assuming degrees and not radians btw). But the sine wraps around, so sine(360) = 0, sine(450) = 1, sine(540) = 0 and sine(630) = -1 etc etc. So if you started your seed at 0 and just counted upwards you would find that regardless of your number of seeds you would get a small limited set of output from your algorithm. In the example I have used eight different seeds (0, 90, 180, 270, 360, 450, 540, 630) but I have only got three different outputs (1, 0, -1), and to make it even more annoying the output of 0 occured at twice the rate of the others.
The algorithm is the hardest part in any procedural system and while you must ensure that you have a sufficient number of seed-values the only thing you can do with your algorithm is to sit down and analyze it (using pen and paper essentially) to convince yourself that you aren't designing an algorithm that has a limited output.
The algorithm also comes into play in terms of "sufficiently different".
For example, if we wanted to procedurally generate a horizon then we could from left to right generate a sequence of numbers that represents the height of the terrain. For example:
0 0 0 0 0 2 5 19 7 4 0
could be taken to mean a "level horizon" that happens to have a high mountain visible to the right. The problem is that the same algorithm, but using a different seed (for a different horizon then) might produce the following output
0 2 5 19 7 4 0 0 0 0 0
which is clearly different, yet if you saw it you would likely say "oh it is just that darn mountain again". On the other hand, if the second example were to also have a moon visible then suddenly you might feel "oh, not seen this before". So then suddenly it is the planetary system that is of interest as a whole and not just the individual planet.
The "final" problem is one of testing. If you have one trillion planets then no-one will be able to go through them all and determine that they look sufficiently different. Not even a machine could do it because if would be to costly (in terms of time) to generate them all and then compare them. For a game you would likely do the player's starting position plus the X nearest stars and a small random selection of the rest. Based on that you would say "good enough" (or reject it and try another algorithm). Part of this is that if the repetition occurs at a sufficient distance apart in the game, then you would likely not recognize it for repetition anyway.
So there are things you need to do, like ensuring that the number of seeds available is sufficient, but when it comes to the algorithm it is the black art (*) of trial and error, experience (****), some qa and a lot of gut feeling.
And then we haven't even got started on issues like trying to obey the laws of the universe as we understand them today (ie, a gas planet is not likely seen in some orbits around some stars etc) - but a lot of this just complicates the algorithm rather than being a specific problem by itself.
So the short reply to your question: Hard work and lots of numbers, but we can never be completely certain (***).
Stefan
(*) btw, we all belong to Slytherin here.....
(**) Anyone who reads this as "Elite IV will contain one trillion planets" will have a spanking coming right along. It is a hypothetical number used to illustrate the problem of scale. Nothing more. Nothing less.
(***) Now if the galaxy only contained four stars...
(****) It helps that there are research being done in this area, and oddly enough cryptography is also a useful research-area for this.
