There are the barren planets, true (although some are not really barren...), but do all the planets really have to have civilization (or have had one)? Surely not every planet in Andromeda is colonized and there must be some virgin ground somewhere? So, how about adding these? Just a simple additional "die roll" result in the phase that spawns POIs on a planet: 10% chance (or whatever you choose...) of there being no POIs what-so-ever on the planet. Nothing else would be required. Simple "skip spawns" if probability happens. You could then occasionally find one of these virgin planets and it would be something different. Maybe you'd want to make one of them your own or maybe just enjoy the view. The galaxy map has something like 10,000+ planets so even if 10% were non-colonized that would still give you more planets with and without POIs than you could ever explore in a single game, so no real downside but you'd add something new to the game. There would be an additional benefit from these, too. Once you have a noticeable number of empty worlds in the game for player's to discover, that would allow you to also generate "exceptions" for them. Like, a unique POI. Spawn one special POI on one of these empty worlds and nowhere else and keep that planet otherwise empty of POIs. This would be a special POI. That would add a big discovery element to the game plus you could also use it as a story element in the missions. Even if you don't have it in the missions it would still contribute to the late game play of Empyrion. It would be a goal to find one of these. Of course, you can't go overboard with these but if you kept the number of these "under 10" and each of them would be unique and geared towards late game and already high-level players these would be just the thing!
There already are empty worlds? In the vanilla game? I.e. "animals and plants yes but no POIs", not the "barren worlds"? By "non-faction space" I assume you mean the star systems that are outside the territorial spheres in the galaxy map, right? I should then definitely explore more, because I haven't found one... There really are?
Yes, it's random though. Each system has I think a 50% of having Warlord and a 50% chance of having Colonists (and a lower chance of other factions). So yes if I am remembering the numbers right you can find systems with no faction presence. Maybe some abandoned POIs but that's it.
And it is so since a long time as I remember to have found Snow Planets without ANY Faction, just Resources, Plants and Wildlife