If you are in France or some other central European old Kingdom, the people living in those castles were the ones who either put the king in the throne or had the power to remove him if he started some funny business, so it was their kingdom in a sense. The problem with modern platforms is, as always, how much leverage the users have against the administrators.
Removal of a bad king was a possibility, but actually attempting to do it was ... tricky. It could definitely backfire and end up with the rebels on a scaffold, or, worse, with a decade-long civil war that harmed everyone and opened the door of the kingdom to potential raiders from the outside.
In practice, unhappy nobles would often rather deny their necessary cooperation (at war or administering the land in peace) and thus force the king to make some amends and tradeoffs.
Well, there is the practical purpose of legitimacy. It may seem too soft for modern power theoreticians, but the legitimate king has something that cannot be acquired by raw power, and that puts somewhat of a damper on potential rebels. Not on each and every one of them, of course, but it has a wide effect. Killing or deposing the legitimate monarch was a serious spiritual crime for which one could pay not just by his earthly life, but in the afterlife as well.
Even usurpers like William the Conqueror tried to obtain some legitimacy by concocting stories why they and nobody else should be kings.
We still see some reverbations of that principle today. Many authoritarians love to "roleplay elections", even though they likely could do it like Eritrea and just not hold any. It gives them a veneer of legitimacy.
Would-be rebels don't necessarily need to kill or even depose the monarch, if the monarch's power is so limited in the first place. They can just go about their business and ignore the king's objections to the contrary.
Then, of course, legitimacy itself is culturally defined, and in some places being able to depose the monarch would be ipso facto proof of said monarch's retroactive illegitimacy. The notion of "divine right of kings" is far from universal.
Yes, in the case of Scotland there is a famous document (Declaration of Arbroath) that was written to the Pope asking him to, amongst other things, acknowledge that Scotland had been pretty much always been independent of England. This was "signed" by the Scottish nobles and has a section saying that if the current king (Robert the Bruce) wasn't good enough at fighting the English he'd be removed and they'd find someone more capable.
