Indeed. Procedural generation can even happily cope with the celestial mechanics. The process can generate the number of objects, and their positions (i.e. where they are on their orbits) as of a specific point in time (say 1 jan 3000, just to have a reference). The position of the objects at any later point in time can then be quickly calculated from orbit times. So all the objects can 'keep moving' with very little storage required, but the need to do lots of calculations whenever the detail is required. In my line of systems design, I call that approach a form of 'lazy execution', which we regularly do by not calculating stuff immediately it has logically changed, but only when it is needed, and since it is often the case that stuff changes again before it is used, you end up not needing to do it at all.
So all the stuff to support first discovered tags, etc., probably adds considerably to the storage requirements, since that cannot be generated on the fly from random numbers. Indeed, it may already represent most of the system state storage needs, and that proportion will get larger as more and more stuff gets discovered, and so more stuff has to be stored. I suspect the absurdly long times required to 'sell' your exploration data is a side effect of this design.
