Xeno,
I think there is a context where we can talk about a government's legitimacy. For example, an opportunistic usurper is illegitimate in a society where kingship is based on hereditary succession. The same could be said of a military coup in a society with a long tradition of democracy. However, this allows the possibility that legitimacy can be acquired, and has the implication that all governments were at one time illegitimate.
For these reasons, I don't think it's productive to talk about legitimacy in the context you have outlined. That doesn't mean I think political discourse is necessarily unproductive. However, I don't see the point of discussing a fluid concept as though it were immutable. When it comes to the relevant context you outlined, I believe political authority depends on possessing the resources to gain compliance. The ways this can be accomplished include mythical indoctrination, appeals to popular or institutional sentiments, the use of coercion, and appeals to reason.
Personally, I prefer that governments primarily rely on reason. Meaning, that the government justifies its authority by serving a rational function, such as providing services including security, law and order, basic welfare, civil rights, and education etc. I also like it if that government is transparent, actively minimizes corruption, and upholds values like equal opportunity and meritocracy. If my government can deliver those things to my expectations, then I am glad to give it my allegiance.
Now, I'll probably give my compliance to a government that does not meet my minimal expectations to the extent I can tolerate it. For example, I can tolerate giving 10% of my earnings to thugs who deliver very little and act like buffoons but generally leave me alone. Nevertheless, I will not defend those thugs if they get themselves in to trouble. However, if those thugs take 90% of my earnings and actively attempt to terrorize me, then they have made an enemy for life who will deliver the fiercest justice upon them should the opportunity become available.