I think we should have the ability to form new Duchies but it should be harder than convincing a few people to switch votes. Maybe requiring the official approval of the King in order to legitimise it? The Kaiser in KotR had quite an important role in assigning new provinces, which meant that Houses couldn't afford to risk alienating him. If the King could officially sanction rebels of Dukes then it would create a sense of risk to go against him.

I also think that LotR flopped because of a lack of competition. There was simply too much land to go around. No one threw the kitchen sink into to getting a certain province.

A key element in KotR was stability. The four duchies were there to stay, and so you could make long term plans. In LotR, you were never sure whether a house would exist by the next term which made alliances riskier.