I think this is getting to semantics, but revealing semantics. I would say a situation where "violence-suppliers form a cartel and people are happy about the way it serves them" to be a wordy way of saying the State. And the same agglomerating forces that lead to a cartel in the first place make it difficult for another violence-supplier to appear: if it offers a better deal to customers than what the cartel is offering, the cartel will point its guns at it and say, "are you sure? You should reconsider."
That's why "private protection agencies" really doesn't get at their nature: being plural is contradictory with having a single cartel supplier of violence. And it's hard to say "private from whom" when there's only one party you negotiate with. And when you're negotiating for protection from violence with the only likely source of that violence... the word racket comes to mind better than protection agency.
It's a valid argument that private protection agencies may become de-facto government. With one crucial distinction: no one's giving them any legitimacy to be one. If they point guns to people, people are free to organize themselves and fight or hire somebody else to fight for them. Either way, it would put a cost on the protection agency. And as we determined, it is always more costly to fight than to strike a deal, even if you're stronger. Wouldn't you agree then, that the equilibrium would be reached in which protection agencies act more like actual businesses serving their customers, rather than as racketeers?
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.