Here's something that just came to my mind. A lot of the time people whine about how private arbitrators are only legitimate insofar as parties agree beforehand to be bound by their ruling. Well, if the government's "justification" rests on the so-called social contract, how is its legitimacy any less contractual? That means its own courts are also only binding upon individuals that have a contract with it. It does no good to simply assert that it is uniquely situated by being the only possible court in the land, because again this is predicated on acquiring prior agreement of its subject-citizens and this is, logically, revocable at will. So essentially, when a statist complains that private courts rest solely on agreement, how does this differ from government courts, except in that the contract here is a real one? Incidentally this is a problem with Hobbes's social contract theory, that if promises will not be kept in a "state of nature" (a premise of his), how exactly does he expect this "contract" to get off the ground in the first place? If promises are kept, the whole matter is trivialized.
Freedom of markets is positively correlated with the degree of evolution in any society...
The chief difference is precisely that, for private arbitration, the contract is real - while an hypothetical / tacit social contract is no contract at all; the essence of a contract being the expressed consent of the parties to be bound by its terms. Hence, the statists' comparison is fallacious at best, if not completely hypocritical, as it's actually assuming what it'd need to prove (ie, the fact that the social contract is a real contract and that people agreed to be bound by the authority of the state).
The fact that it is (or not) the only court system in the land is irrelevant. You could have a private monopoly over courts and that would be ok as long as only the people who signed for its services are bound by its rulings. This is, in fact, how Nozick derives his minimal state from a state of nature without breaching individual rights in the process.
Re/ Hobbes Leviathan, several philosophers have refuted his claims on the exact grounds that you mention. From what i remember, James Buchanan, David Gauthier, Loren Lomasky and Jan Narveson all raise this argument (among others) against Hobbes' social contract.
I mentioned the above because I recalled a statist arguing that private courts are mock courts because they are only binding on people who agree to them. it got me thinking, that if state courts are based on a "social contract", that they're scarcely better, and in fact worse off.
Funnily enough, i had no later than yesterday a similar argument with a lawyer, who was claiming that private contracts enforced by private arbitrors or conflicts settled by mutual agreement of the parties are not legal. It took me a while to make him admit that law does also include private- and not only public-law.