> Crime prevention? Does our government police prevent crime, or just punish criminals?
Both.
> I can argue that without any state-established law criminals would be punished, in some way or another.
Without any state-established law there would be no criminals, just the much broader category of people that other people don't like. Quite arguably, the whole purpose of state-established law is to limit the scope and severity of punishment compared to what happens in the absence of central authority, and to provide clear rules. This aids in deterrence, since, to the extent that antisocial behavior is rational and deterrable, there needs not merely be an expectation of punishment if you do 'wrong', but a clear idea of what 'wrong' is in the context, and a clear expectation that punishment will not be imposed if you do not do 'wrong'.
Certainly, one can argue that modern states are less than ideal in each aspect of this, but that's very different than arguing that they are worse than the absence of a state would be.
> Medical services? I think that some people really enjoy being doctors and nurses, and they would associate even without state-mandated organization.
The problem here isn't that there would be no medical practitioners apart from a mandate to provide them (after all, most states that provide medical services don't compel people to become doctors and nurses), but that medical services lack features that make it the kind of service modeled well by econ 101 rational choice assumptions, with (among other things) a very high and uncorrectable cost of bad (or even merely incompetent) suppliers.
> But we're (slowly) solving scarsity through science and technology.
We may be reducing the resource costs of some goods and services, but that doesn't solve scarcity (it reduces the opportunity cost of some while increasing the opportunity cost of others, since it is unequal progress, and opportunity cost is what else you could have gotten for the resources you put into getting what you chose.)
Suggesting that we are "solving scarcity" demonstrates a lack of understanding of what "scarcity" means.