First, I'll start by saying that I define anarchism as “libertarian socialism.” That is, classical anarchism. Anarchy means “no rulers,” and anarchists have traditionally taken that to mean no kings, no bosses, no landlords, etc. The kind of rulers that arise from capitalistic property are still rulers. Communist anarchism proposed communal ownership with democratic management. (Cf. Kropotkin, Malatesta, Bookchin) Mutualism and collectivism had a more nuanced approach, still with some sort of public ownership and democracy. (Cf. Proudhon, Bakunin) Then there was individualist anarchism, which wished to abolish allodial and fee-simple property, as we have under capitalism, and replace it with usufructuary private property and totally free markets. (Cf. Benjamin Tucker, Thomas Hodgskin, Lysander Spooner) In all cases, anarchists criticized rulers across the board. They disliked political rulers (kings/politicians), disliked official rulers (cops/theocratic priests), disliked economic rulers (bosses/landlords). “Anarcho-capitalism” is a departure from classical anarchism. While it has anarchistic tendencies and influence, it is not entirely anarchist. I don't call an “anarcho-capitalist” an anarchist for the same reason that I don't call a kid throwing a brick an anarchist. Anarcho-capitalism says that it is okay for people to be ruled over by bosses, because they have voluntarily entered into that arrangement. They say it's okay for a landlord to make rules for his tenants, since the property they live on is his. Thus, anarcho-capitalists consider any sort of rulership deriving from legitimately acquired property as being justified. Regardless of whether or not it is true that property can justify rulership, it is the case that anarcho-capitalists support some types of rulers that classical anarchists rejected, so anarcho-capitalism is a departure from the anarchist position.

Furthermore, when I was an anarchist, I identified with the classical anarchist tradition, being influenced mostly by Proudhon, Bookchin, and Benjamin Tucker. I advocated a free market with either usufructuary or Georgist private property within a system of democratic confederalism. Plus, anarcho-capitalism didn't exist when Morris and Shaw wrote these critiques of anarchism. So, it made sense to exclude "anarcho-capitalism" from the discussion.

You said: ”How can a state police service (South Africa) be an example of decentralisation?”
I was actually referring to the decentralized and competitive private security forces in South Africa, which operate much like the system that anarcho-capitalists advocate. Check out Law and Disorder in Jahannesburg. Btw, there actually are some aspects of Rothbardian security theory that I agree with, which I have written about here.

You said: “And he was WRONG. Socialism did not bring social equality, did not eliminate class structures and hierarchies, and has not removed the ability to have power over others when & where it has been tried.”
Actually, democratic socialism in Norway, Sweden, Denmark, Iceland, Finland, has done exactly that. And these places only ever went partially socialist, not fully socialist. Where “socialism” has not worked is in places like Russia, where socialism was NEVER tried. Lenin, following Marxist analysis, thought that socialism could only come about with the full development of capitalism; cut-throat competition would lead to monopolies, which would then naturally be taken over by municipalities like natural monopolies such as water and electric companies were. Since Russia had a pre-industrial agrarian society, rather than a competitive market, when the Bolsjeviks took power, Lenin believed that “State Capitalism” (Lenin’s own term, btw) would have to be employed rather than Socialism. Instead of worker-owned cooperatives, Lenin opted for government-owned industry—State Capitalism, not Socialism. He thought that eventually the State would “wither away” and socialism would naturally emerge. Either way, I am more of an advocate of distributism rather than socialism, so it’s a moot point.

Also, you mentioned “communism” as requiring a State. Actually, that's completely untrue. Communism is defined as a stateless and classless society. Such things do exist, but usually only in small tribal “primitive” communities. There's a great deal of sociological and anthropological literature on the topic. (Cf. David Graeber’s works on anarchy in Madagascar and James Scott's The Art of Not Being Governed) Also, the communist idea of “from each according to ability, to each according to need” is the bedrock of our society, what governs our relationships with families and friends. You don't tally up points when your kids get food from the pantry. This is what David Graeber refers to as the "communism of everyday life"; sociologists and anthropologists have been talking about this for a couple hundred years now.

You said: “capitalism has never required a state in order to work.”
Actually, the opposite is the case. All real stateless societies have been based on primitive communism or gift economies. Capitalism has only ever emerged where States have come into being. One government invaded another, looted, and took all the gold; they then minted the gold into coin, gave it to the soldiers as payment, then required the subjects, conquered people in general, to pay taxes in this government-issued coin. The necessity of acquiring the coin in order to pay taxes created a general demand for it, bringing markets into being. Barter, contrary to classical economics’ claim, never arose anywhere until after monetary systems had existed and collapsed. There is a great deal of archaeological and anthropological literature and research to back this up. (Cf. David Graeber, Debt: The First 5,000 Years)

You said: “A government is and will always be unable to optimally regulate markets of any kind, because it cannot know all of the inherent needs and wants of the market and all the consumers within it.”
I am familiar with the arguments against central planning. I actually agree with them, as does Karl Popper. That’s why both myself and Popper advocate markers for the distribution of goods rather than central planning. You should check out my post Markets Are Not Perfect, where I look at a few instances of market failure and how government intervention can rectify the problem. And, for the record, I am both pro-market and against central planning.

You should check out Markets Not Capitalism (book) for a look at a more classical market anarchist perspective, one that isn't exactly anti-Rothbardian btw. Also, maybe check out Benjamin Tucker's Individual Liberty, a classical market anarchist work. Tucker and Spooner heavily influenced Rothbard.