So this "legitimacy" you speak of... you suggest that it is determined by whether the gun-toting thugs are sufficiently "liked"?That magic is called "legitimacy", a basic condition for governing according to wikipedia. When a people decide they like one group of gun toting thugs more than all the other groups of gun toting thugs, they call them a government. As you say, it is quite normal. If a government loses its legitimacy then it should, and probably will be replaced with a new group of gun toting thugs, unless there is some magical third option that you will reveal to me in a condescending manner after casually dismissing each of my points (I assume this is where you are going with these annoying hypothetical situations, it's just getting a bit too abstract for me).
Liked by who?
And if the majority still likes them, do their actions continue being "legitimate", no matter how horrific?
Is that how it works?