Well, who's giving the State its legitimacy right now?
It's not some god in the sky that does. We do: not just a generic we, but most people reading this, you and me included. We choose to participate in the markets it establishes; it tells us what property rights are and says they're property rights because it says so and has the guns to back them up. The corporations we work for rely on it to break down people's doors when someone gets ahold of a next gen device that they misplaced, and we feel safe that the money we put into our banks is safe for us because the State will yell at the bank if it takes our money and pay for it if the bank loses it.
There's no reason a protection agency wouldn't do the same to establish its own legitimacy. It seems like a good business model, in fact: convince everyone that questioning it is morally bad, create some ideal of "citizenship" that amounts to brand loyalty to violence, and then expropriate value from a populace that's not only cowed but actively consenting.
Don't get me wrong: it gets my goat as much as yours that that's the situation. But I wasn't describing before how a hypothetical, ahistoric government-like entity might develop: I was offering a general theory of how it actually did. If it's right, the State isn't some aberration but an emergent, self organizing maelstrom that has gradually grown to envelope virtually all people in all places.
My issue with libertarianism as it exists in popular culture is that its idea of liberation seems to be getting the State to deign to rewrite property rights to privilege one part of society instead of the current one (that's all of electoral politics, actually). Once that's achieved, one gathers, we can all become happy and free consumers because a certain property right regime has become the law of the land, imposed from above by our now-purified and almighty State.