Sim, os aumentos de crime são evidência de que o estado, no caso, está falhando em detê-los. Mais ainda quando são crimes perpetrados pelo próprio estado. Em alguns casos pode ser que a iniciativa privada fosse ser melhor do que o estado nessa tarefa.
Mas meu ponto não é exatamente que "anarquia não dá certo", mas mais especificamente que as economias de mercado mais eficientes que se observa não são aproximiações da anarquia; são aproximações do que se sonha que a anarquia fosse ser, se viesse a existir. Mas a realidade é que essas economias de mercado presentemente existem justamente sob estados altamente funcionais, com forte correlação entre ambos. Não em estados insignificantes, se fragmentando, se aproximando da inexistência efetiva.
Essa correlação, bem como as problemáticas outras argumentáveis (e "indesejáveis") aproximações reais de anarquia, tornam bastante difícil levar muito a sério colocações extremas como "o Estado é desnecessário para o bom funcionamento do mercado. O Estado atrapalha o mercado". O que se observa geralmente (no mundo real) é que ambos estão funcionando melhor conjuntamente (conforme os gráficos do Heritage.org).
Estado ou iniciativa privada, o que se tem são "as pessoas fazendo coisas". As distinções entre um e outro não são suficientes para que um seja universalmente mau e fadado ao fracasso ou a piorar as coisas e o outro bom e destinado ao sucesso, como crêem apenas os comunistas e/ou anarquistas. E ambos são provavelmente inevitáveis se não estivermos considerando apenas ermitões isolacionistas com território amplo o bastante para não haver sociedade, ou uma utopia mágica onde todos têm tudo o que querem, de alguma forma.
Inclusive "Estado" é dificilmente distinguível do corpo de leis privadas e órgãos associados que se admite terem que emergir em "anarquias", tornando-as inevitavelmente em estados minárquicos (inicialmente), reconstruídos do zero, apenas talvez com poder executivo totalmente conduzido por entidades privadas e de acordo com essas leis, diferentemente do que costuma acontecer no mundo real quando a iniciativa privada compra ou substitui ao estado.
Tendo dito isso, não prevejo impossibilidade absoluta em "anarquias" funcionais, especialmente se aceitarem a economia de mercado. Mas deixo ainda as aspas em "anarquia" por que, como disse, a coisa deve inevitavelmente rumar para um estado mínimo, ainda que "tribal" ou algo assim. Parece que a maior parte das tentativas de criar novos países por libertários nem tem tanto de "anarquia" no discurso, mas não acompanho isso realmente.