Personal rather than bureaucratic governance has been the rule through most of human history. Your idea that bureaucratic rule, based on the rule of law is typical of how pre-modern socieites have been governed is not accurate. Feudal governance, what we are talking about here, is largely personal in character. The throne rules when there is a militarily powerful, forceful personality on the throne; when such an individual isn't there, governance is largely local; the role of the king recedes into the background.
The power of rulership is exemplified by the ability to get people to do things because you said so. Those who have military power already have that ability (they got an army to follow them), those who have "forceful personalities" are able to gain that power by virtue of such. But just being charismatic or strong by yourself doesn't do anything for your power. You have to be able to manipulate others, and when you manipulate others, you form a system of governance, and that system of governance outlasts your personal power, or your empire dies with you.
The kings may have been more or less influential depending upon how good they were at manipulating the institutions, but the very fact that they could be called Feudal Kings shows that it was the institution of feudal kingship that ruled the people, not the individual kings. Their devotion lied toward the office, not toward the individual, which is well-shown in your example: when the king wasn't a successful ideologue, they didn't get a new king, but rather had more powerful local idealogues take the center stage without disrupting the overall system. The Kingship lasted, and those who gave the Kingship power (the local lords, the church) obviously were able to wield more power as a whole than the one guy on the throne.
On what basis do you make this claim?
The practice of polytheism isn't the practice of choosing one god over another in a world full of gods, but rather devoting oneself to the correct gods for the job. There were never Priests of Odin and Priests of Thor, there were kings and warriors who paid them both devotion when either was due it. The polytheisms that break this rule tended to be not one religious system, but many shoehorned together by an empire, nation, or tradition (such as Egyptian polytheism, with it's heavy geographical influence). I make this claim based on what polytheism is for those who practice it, which is not just a bunch of competing monotheisms, but rather one system for dealing with the supernatural world (which is part of why conversion to monotheism is often seen as easy -- polytheism easily accomodates new spirits). The image that comes instantly to mind is the Patamuna. They may have competing shamans, but each type serves a different role in the community that the community as a whole accepts as the real way to deal with the spirit world.
In ancient Rome, Platonists, Aristotelians, Pythagoreans, Epicureans and Stoics competed for the role of defining the overarching social, moral and metaphysical system that the universal belief in the gods entailed. Similarly, in China, Buddhists, Confucians and Taoists competed for this role. Even in India, where the Brahmin caste existed and Vedic thought had a special place in defining the social order, Vedic thought nevertheless competed with Sikhism, Janism, Buddhism, etc.
Platonism isn't polytheism, though, and neither are (most kinds of) Buddhism, Confucianism, or Taosism. In fact, many of those Roman and Chinese philosophies lacked any kind of real theism at all, being more concerned with a moral guidance than the world of the unseen. These philosophical systems absolutely competed, because their ideological control is key, but that's no different from the myriad Christian sects or the sweeping variety of ways to run an
umma correctly, or the different ways of practacing Judasim. They are all about ways to change existing structures, about institutionalized ideological control, which means it is the belief and the structures that maintain it that is more key to the rulership of a nation than the person who espouses such beliefs.
Polytheism itself is no way to run a nation, but ideologies based in those assumptions absolutely can be.
So, what institution are you talking about?
The institutions of governance and rulership, the tradition of the people, the logistics that allows public works, the framework of the military, the designation of a holy site, the power to manipulate people through established, transcendant authority that goes beyond the individuals excising that authoirty.
Feudal Kingship is an institution, a tradition, a particular order to things. That way didn't change drastically for hundreds of years because people believed in it, not because they believed in individual kings. When this institution loses that ideological credibility, it falls, as so many Chinese dynasties have.
Since when!? Again, you are acting as though the way government works in the 21st century can be helpfully generalized to the past.
You're using a lot of demands and presenting my argument for me. Do you want to have a conversation, or would you just like to go on assuming that I'm wrong and sure of your own veracity? Because while I'm interested in talking about the underpinnings of faith and devotion as nessecary to the operation of a successful rulership, I'm not really interested in trying to win an internet argument, so if it's the former we can talk, and I'd ask you to listen rather than assume my actions smack of ignorance, and if it's the latter, I'm wasting my time either way, I guess.
Rulership is evidenced by getting people to do what you want. If you get the peasants to pay their taxes, go to war for you, and say "Long live the king!" congrats, you're a successful monarch. If you have a revolt under your rule and managed to be killed by a bunch of revolutionaries, you're not. Rather, the leaders who got them to revolt are the successful rulers. People won't do what they don't believe in unless forced, and force only gets you to get them to do it 'till your back is turned.
It's the difference between the Intimidate skill and the Diplomacy skill.
Make a game mechanical argument for why this should be true.
The mere existence of the Aristocrat class implies that some people rise to the top despite not being ludicrously mighty weavers of magic and steel, that there are some things birth or wealth can get you that slaying orcs cannot.
How is this skill focus necessary to convince the court that you can kill them all in 12 seconds? All this skill focus would do is confer +3 to a diplomacy check or whatever. In my view, the circumstance bonus conferred by killing people to such checks would be decidedly larger.
It's not nessecary to bully the court into acting, nor is it wise. This would quite obviously be a use of the Intimidate skill, not Diplomacy. And Intimidate doesn't last long, nor does it get people to follow you unless you remain constantly in their presence.
Rather, convincing the court that you are right, that you should be supported, and that you are the man with the right knowledge and skills and blessings to lead to prosperity is, at it's most cruel, a Bluff check.
Even game-mechanically, threats of violence are not the best way to lead a group of people.
Historically, think of the Bedouin conversion to Islam. The Bedouin were undoubtedly stronger, tougher, faster, and better warriors than the civilized folk of Mecca and Medina. In order for the Islamic Empire to even come to first fruition, it was nessecary for the Bedouin to embrace a theology of a militarily weaker people, an ideology that they didn't need.
But government by stable bureaucratic institutions based on the rule of law is an incredibly recent development.
Institutions are a human norm, from the rites of initiation in tribal societies to the Catholic Church, people look for traditional systems to measure new changes by. It's not based on the rule of law, but on the human desire to believe in something beyond themselves, on the imaginairy sphere of faith, devotion, and ideology.
Maybe "institutions" is too precise a word. Traditions? Social structures? Whatever. The point is that it is the system that has power, not the individual players in that system. Those who manipulate the system the best can excise more personal power than others. In D&D, this isn't measured by level precisely, but in a host of skills that many adventurers choose not to advance, thus making most adventurers rather poor rulers (though great people for the rulers to have around).