In the dark world of the Warhammer 40000 there is only war... and where is war, there are victories.
While the Imperium is stagnant, the never-ending conflicts mean that the borders keep shifting between various forces: sometimes the xenos or Chaos steal a world from the grasp of Mankind, sometimes its the other way around - a lost colony is brought back to the light of the Emperor. For example, Eisenhor says:
More often still than politics and ethics, we talked of history. Again, in this area, his learning was tremendous, but there was also, for
the first time, an eagerness, a hunger. He never asked directly, but it was clear he longed to know in detail about the events that had
taken place in the two hundred and twelve years since his death. His family had clearly told him little. He made leading remarks to
draw answers out of me. I gave him some, and sometimes volunteered accounts of major events, political changes and Imperial gains.
I had decided beforehand not to make any mention of Imperial defeats or losses, to avoid giving him anything he might relish. The
picture that Pontius Glaw got from me was of an Imperium stronger and more healthy than ever before.
This means that while the inquisitor was manipulating the truth, he wasn't outward lying - the Imperium was gaining new planets.
In the "Soul Drinkers" series, there is a mention about a planet that has been recently annexed:
WHEN THE PLANET Veyna was annexed by the Imperium in 068.M41, it was a Halo Zone world marked out only by the lakes of
liquid nitrogen at its polar caps and the small civilisation that clung to survival near the equator. These people were the
descendants of settlers from the Scattering, the great drive of colonisation that seeded the galaxy with humanity after the discovery
of warp travel. Veyna was one of the many worlds that had been forgotten for thousands of years, cut off by the Age of Strife and
bypassed by the Great Crusade, only to be rediscovered in the second half of the forty-first millennium.
There were hundreds of worlds like Veyna. Most of them never even had names. Isolated and backwards, feudal or black powder-level worlds, gradually drawn back into the fold by the ravenous Imperium that considered itself to own every community of
humans in the Galaxy - including those they hadn't discovered yet.