A Belated Reply to Brad DeLong
To make your case, you have to show that societies without state law enforcement have consistently worked worse than otherwise similar societies with it. For a little evidence against that claim I offer the contrast between Iceland and Norway in the tenth and eleventh centuries or northern Somalia pre-1960 when, despite some intervention by the British, it was in essence a stateless society, and the situation in the same areas after the British and Italians set up the nation of Somalia, imposing a nation state on a stateless society. You can find short accounts of both those cases, as well as references and a more general discussion of historical feud societies, in the webbed draft of Legal Systems Very Different From Ours, a book I'm currently working on; comments welcome.
So far as the claim that the idea of societies where law enforcement is private are a recent invention, that is almost the opposite of the truth. The nation state as we know it today is a relatively recent development. For historical evidence, I recommend Seeing Like a State, whose author goes to some lengths to make it clear that he is not a libertarian while giving a perceptive account of the ways in which societies had to be changed in order that states could rule them.
In which context, I am curious as to whether you regard yourself as a believer in the Whig theory of history, which views it as a story of continual progress, implying that "institutions A were replaced by institutions B" can be taken as clear evidence of the superiority of the latter.