Technology has come a long way in the last 1000 or so years. I suspect that there are new solutions to the problem that you describe. But they don't get explored because the State has a monopoly on violence and is very resistant to change.
Most of the time that's a good thing as it means that things get screwed up only very slowly. But it also tends to prevent things from getting better, too. Only the most egregious problems get solved.
Also, because most people consider the State and its monopoly on violence to be a perfectly adequate solution to the problem.
Then give a concrete example of such a solution. The current system (having a state actor) works more or less well in preventing power abuse by private entities. But shouldn't we wait with abolishing it until we have actually found a better solution?
No, wrong. Alternatives get explored all the time, and radical changes in the dominant role of social organization have happened over the 1000 year time period you discuss. You've anthropomorphized the abstract concept of the State improperly: the state is whatever entity or collection of entities taken together have a monopoly on legitimate violence, but the entities or collections which do that over time have changed quite rapidly -- the modern nation-state system is only a few hundred years old -- it is a fairly new model -- and there has been considerable evolution within that model (and its one that has been widely perceived as weakening in the face of evolving, powerful, non-nation-state actors of various types.)
When there's a technological revolution every 20 years or so, but a political revolution only every 200 years or so, I think it's fair to argue that the state is very resistant to change. I might see several technological revolutions in my lifetime, and no political ones.
And what he's saying is "The thing underlying the veneer is pretty savage, which taints the idea that everything is so civilized"
That's a point you seem to completely miss.
If the counter-point is that you can escalate the situation by attempting to resist the state's monopoly on violence, then sure. I concede that. I don't believe the thing underlying the veneer is savage. Quite the contrary.
So if you think you shouldn't have to pay taxes, because the state isn't a legitimate authority, it's quite likely that you'll end up dying.
Finally while taxes aren't collected directly by a person with a gun, failure to be sufficiently subservient while dealing with the state can result in your death. It's unfortunate that the state grants itself (in all its forms) much, much more privilege or leeway than any non-state actor would enjoy in a similar dispute.
In other words, if you fail to pay a debt to another citizen or non-governmental entity, it's usually handled much, much differently than failing to pay a debt to the government. That double standard definitely doesn't feel right to many folks, and I think that's a very reasonable point to make.