Fair points. However, without real-world examples, simulations or such-like, we're both speculating about what it "would" be like. ;-)
I hate to bring that place up, because of the inevitable "Why don't you move there you think it's so great?" stupid comments, but we do have real world examples of private security in Somalia. Those "roving bands of warlord mercenaries" have settled down and set up territories they protect. If you live on their territory, you pay them protection money, and they keep the peace within the territory, and keep bandits and others at bay. If you want to own a weapon to protect yourself, you can do that too. And if you don't like their service, you are free to move; they won't stop you. The "war lords" have long since become professional businessmen rather that bandits and looters, who have not only realized that they can do better by providing others with a service rather than stealing from others, but now actually take pride in protecting their territory and their people.
As for the arbitration thing, that's how it works already. Especially now, with globalization creating multinational companies that don't operate under a single country. There is currently a special set of international laws being worked out, based on general consensus among large businesses rather than some country's legal precedent, which has to rely on arbitration, and businesses forming contract agreements decide which arbiter they wish to be involved with.
Also, don't confuse criminal law with contract law. If you're dealing with a business, and they screw you somehow, you deal with contract law and arbitration (or civil court). If they use their power to screw your property or steal your money, that's a crime, and you deal with that using criminal courts and force, which may include people with guns. It really is no different from how it works now.
Here's a thought experiment:
What if one such person decided that the road to riches and power is to become the greatest, most popular arbitrator in the land? S/He could set up a court that works differently from the others. They've recognised that justice behind closed doors and where money mysteriously changes hands is always going to be a bit iffy. So they've found a way to make it fairer by making it free. The contestants don't have to pay anything (outside of the actual judgement), it's the audience that has to pay to watch -- a real spectacle! Much like a talk show host, the arbitrator is "in charge" but only has his oratorical skills (and nominal security guards) to influence his voluntary audience who cheers with approval, or boos with disgust.
A master of suspense and manipulating large crowds, the arbitrator levers his audience to give his judgements more oomph. After all, what is a judgement worth if a) nobody's there to witness it, and b) nobody knows they should help enforce the findings? This way, under the threat of an angry mob, even powerful, "reputable" companies must graciously compensate the little guy who has been wronged.
I think you misunderstand the purpose of such legal disputes. The value of arbitration, i.e. the legal dispute, is not in how much you pay the lawyers. What businesses look for is someone who can fairly decide for, and protect, both parties. They are looking for someone who can provide a just resolution for both people involved, or at least not screw them too much if they fail somehow. So this Super Arbitrator providing his services for free won't matter, and they won't be interested in shams and showmanship. Also, the amount of witnesses doesn't matter in these. A decision will be closely watched by any other business involved with those who had the dispute, and depending on how the two parties act after the decision, they'll make their own informed opinions on whether to continue to deal with them. If a business that went through arbitration screwed someone else, or failed to compensate someone fairly, there's a good chance they will be dropped by other businesses, and the business will die. Very few businesses nowadays work all by themselves (you almost always have to buy materials and labor, and sell it to someone else).
You're also forgetting that the angry mobs already exist. They're called consumers, who avoid buying products from companies they don't like. So, again, there won't be much change compared to what we have now.
Just to give you an arbitration example: Let's say company A bought 10,000 widgets for $1 each from company B, and 5,000 of those widgets turned out not to work, possibly damaged during unloading. Company A demands 5,000 replacements or $5,000, and company B claims the widgets were damaged by company B, and thus they don't owe anything. A crappy arbitrator would listen to both sides, and decide that Company A needs to pay $5,000, or that company B is at fault. A great arbitrator would decide that company A needs to sell 5,000 more widgets to company B for $0.25 to $0.50 each, and company B MUST buy 10,000 more widgets from company B at full price their next round. Both companies come out on top in the end.
Thus, the An-Cap revolution turns full-circle. In the absence of old, organised power, newer immature kinds pop up that are more easily corruptible, dictatorial, and make use of a simple "majority rules" system.
You can't have a majority rule or dictatorial system without a government deciding on laws, and enforcing them through forcefully collected money. If no one pays for what the dictator is offering, he won't be a dictator for long.
PS: you can't say that it's unrealistic, as there are plenty of real-world talk shows, etc., that follow this basic format. The only thing stopping them from growing out of control are government laws and the competitive presence of "official channels" for justice.
That, and viewers, ratings, customers, companies wishing to associate themselves through advertising...