I just offered empress of southern empire the dragonbanner.
She said, I paraphrase, "This is the greatest service anyone has ever done for me. I am very grateful".
My relation went from 0 to 2. And the next time we spoke (My character is Thor), she greeted me with "Thor......".
This must be a parody.
Your relationship with lords should be a massive source for replayability. Lords should get a first impression of you decided by circumstance, their needs, their position, your trait compatilibility with their etc. If you save them from defeat or captivity, it should be a significant boost since these chances are not controlled by you.
Befriending a low rank lord should be easier than the kingdom marshal or the king himself.
Games like FTL have massive replayability because you don't know what you are going to face and you have to decide on the strategy as things happen. There are plenty of LEMONS and plenty of LEMONADES. You don't know the direction the game will take or what your approach and general strategy will have to be.
The current M&B2 has a good kingdom sandbox. It is great that the story of the kingdom unfolds generically in a sim. But no doors opens or closes for you during this. You still have to line up at a door of your choosing and scratch at it until it lets you in.
A good storyline would be if I thought I was going with the empire, but I befriended a khergit by chance by saving him from looter captivity and then that relationship indirectly affected a lot of other khergit lords because of that that lord's relationship to other and we fought and lost a khergit civil war which forced us into exile with the battanians and into their service since the khergits now were actively looking for us.
Nothing forced, but certainly a game that opened different doors on each playthrough, then THAT is replayability. A +/- 2 change in relation that is "always" initiated by the player does not achieve this. No course of action becomes more or less compelling by such miniscule adjustments.