* stalemate - player being unable to progress significantly or lose, very slow change of the borders (you get a planet in one place, lose it in another, when you reconquer the lost planet the first you conquered gets a revenge strike from the previous owner)
* player steamrolling if AI is weak - it's quite easy, under lower difficulty setting for the player to massively dominate the ememies.
sounds like a balance issue - either its too hard and you get nowhere, or its too easy and you're "Sherman marching through Georgia".
perhaps dynamic difficulty level would work. behind the scenes, as the player makes progress, difficulty (AI or whatever means you want) increases, and vica versa.
if you think about the scenario you've described:
"a game where you start in already living galaxy, filled with preexisting powers. Theses powers (AI) not playing the game to win, only the player being able to win, the rest just living ther and having their own goals and objectives and, very important, it does not hurt the player if they reach these objectives, there is no "race X has built a trans something machine and therefore won the game: game over"
there are only a few possible way for things to go down:
1. you're weak. its an up-hlll battle. a long grind. perhaps un-winable.
2. you're strong: "Honey, have you seen the keys to my steamroller? i'm late for work!" Can't talk now Shug (Sugar), my Emperor needs me!"
3. a balance of power- the planet swapping stalemate you've apparently seen in play testing.
sounds like you want gameplay balance to fall somewhere between "balance of power" and "you're strong" - so the player makes progress, but not too easily.
its quite possible that gameplay balance changes over the course of the game - at first you're weak, by the end its "steamroller time!". this tends to be a natural part of playing the winning side. things like dynamic difficulty and late game "mechanics" such as outside invasion or civil war to shake things up can be used to keep things interesting from the first turn to the last.
reminds me a bit of my problem with Armies of Steel II - a RTT game. hard coded missions. balancing difficulty is quite hard. i haven't figured out whats wrong, but its just not that much fun. its too easy to just say "everyone go here!" then turn up accelerated time, and see what happens. too easy, you win every time, too hard, you lose every time. and with hard coded missions, its the same every time, so its easier on each replay. i basically shelved the project for now in favor of other titles with better potential and no major design issues.
sounds like play balance is your fundamental issue.if its due to balance changing over the course of the game (IE hard at first, then too easy later on), dynamic balance that changes with player progress might be just the ticket. this might be easy vs hard AI, or nerfing or buffing non-player factions over time, or other methods. note that many / most / all methods might be considered "cheatiing" on the part of the game. that's ok, just keep it hidden and non-flagrant - IE beliveable.
