Sorry this got longer than I thought.
Though I feel it isn't a main point (and giving this reasoning doesn't prove a monopoly will form) I will point out that on the ground sending a patrol to an area is inherently more efficient the more customers you have in that area and that this is a large part of police labour. I'll also point out that once a local monopoly/oligopoly forms if you wish to start a competing company you need to either accept the large capital investment of starting the company for 1/4~1/2 the area (say city) or alternatively you are surrounded by a larger force that has a reason to want you out.
As to whether or not monopolies will form (while in no way proof) I will offer as example that generally throughout history establishments of force (gangs, organised crime syndicates, city states, warlords, tribes, governments) seem to exert the majority of their force in areas of control and it is only at the edges between two of these powers that you have a choice between these powers (and often the area is more dangerous because of it).
As to why governments today aren't on a rampage. I will point out that these governments have effectively formed coalitions or come under the protection of larger allies to allow them to have sole or mostly sole control over their people (A situation that would not necesarily be as nice for a lot of the people if the governments were instead local monopolies on force with no obligations to the populous). Lastly I'd point out that many smaller countries complain about the US/China/Russia as bullies on the international stage and that they have bought force against "startup" force companies (tongue in cheek, obviously) such as say terrorists.
I realise you might be saying the cost of aggression is prohibitive, but I'd say it's the fact that the large players can't advance without being destroyed (MAD) that keeps the system somewhat stable. I'd also point out that the number of countries changes and that generally it seems like there is a trend to consolidation, even if it's playing out over decades/centuries.
>Of course, a more rhetorical approach to this criticism is that even if it happens, you're basically left with a government.
I don't disagree, but it would not be likely to be a government that the majority would want more than the current system (at least in first world countries, as I'm sure you'd agree). What it comes down to for me the fact that the market for force doesn't have as strong external/internal checks and balances. So it would (I believe) likely deteriorate to something worse than what we have now, before moving slowly back through the steps to something approaching our current systems.