I like the idea of nomadic realms but I suspect that in practice they'd be too complex to implement, and wouldn't necessarily fit with the theme.
However, that does give me an idea about how this could be made to work in a historically plausible sort of way (given that the origins of many medieval kingdoms lie in mass migrations of entire peoples):
***
Step 1: Implement the Too Few Nobles mechanic (with forewarning), meaning that pretty much every realm will have several regions revolt to rogue.
Step 2: After a few weeks, and again with forewarning, announce an Era of Great Migrations where entire peoples are on the move and migrating to new lands.
Step 3: Give rulers the options to ask devs to trigger a Great Migration for their realm (granting the request would be dependent on whether or not it was justified by the realm's location in order to prevent the mechanic from just being exploited by realms who want to beat up their neighbours but have no intentions of moving).
Step 4: When a Great Migration is triggered what it would essentially do is give significant buffs to the realm that was migrating on condition that all their old regions would go rogue the next time they conquered a townsland/city/stronghold. The buffs would include things like increasing how many troops could be recruited, reducing sea travel costs, eliminating the distance from home penalty on troop morale, halving how much troops needed to be paid, reduced equipment damage, etc. This should make it possible for them to actually carve out new realms for themselves. The buffs would also need to expire within, say, six weeks of taking a new city/townsland/stronghold.
Step 5: Realms embarking on a Great Migration would obviously recruit a large mobile force and start travelling by land or sea depending on where they want to go to. En route they could loot gold/steal food from the regions they're passing through. When they finally arrive at their destination (either rogue regions or land belonging to another realm) they'd start a takeover. Realms in the areas which migrations are heading towards would then have to choose to either make a deal with the invaders ("we'll give you that city but you'll have to help us against our enemies"), defend against them ("enter our lands and die") or direct them to some rogue regions where there's an unclaimed city/townsland/stronghold.
Step 6: Upon completing a successful takeover of their first new city/townsland/stronghold the migrating realm would see their new region receive additional buffs from the Great Migration ending - such as the relocation of RCs from the old capital to the new region, automatically making the new region the capital, adding basic fortifications and an initial 10k CS of militia, or similar. This should help them establish themselves in their new location while their old regions are made rogue.
***
Now let's think about how that might work in practice using Dwilight as an example. A realm like D'Hara might migrate to Eidlub or Chrysantalys or Shinnen. Madina or Fissoa might migrate to Shinnen or Poryatown. Luria might decide to go to Flowrestown, forcing Swordfell to either fight back or migrate somewhere else themselves, or Luria might just decide to stay where they are and deal with the new interlopers. Or someone might decide they like the look of Gaston and migrate their entire realm there.
Of course some realms might decide to stay in place, and that would be up to them, but I expect that if the goal behind the idea was explained to players then most realms would get into the spirit of things. Additionally, one off buffs with manual dev involvement would probably be a lot easier to code than a whole new nomadic realm mechanic.
After the migrations are finished, what we should end up with, again using Dwilight as a purely hypothetical example, is a lot fewer realms completely separate from their neighbours - ideally we'd see the new realms filling in a lot of the gaps created by regions going rogue from the Too Few Nobles mechanic.
And obviously one consequence would be that some realms would die (either from being the target of a migration or from a migration attempt failing). But unlike previous mechanics (the ice sheets), the migrations would stand a good chance and should be a fun experience. And even when migrations failed they would at least have resulted in an entire realm's worth of nobles ending up in a different part of the map, even if they then are forced to assimilate into new realms. It should be a far cry from realms being put in doomed positions and the players in those realms just being put off and giving up.
That's why I think a mechanic like this might be the best way to rebalance noble densities and is likely to avoid a lot of the pitfalls that previous attempts fell into.
