Govenments are broke... but towns and corporations aren't
From a very practical point of view a government is nothing other than an organization empowered to use the threat of violence to impose order on society. As the history of humanity has proven, "order" is often a very subjective term that should be modified to, "someone's interpretation of order." A military is nothing more than a national "police force" with jurisdictional rules that are a hair more complicated (although today's police would very likely take issue with that statement, their jurisdictional problems are nightmarish). In other words, when a government imposes its version of order on its own citizens, that's usually a task for an organized group of people called "the police." When a government imposes its version of order on another government's citizens, that's usually a task for an organized group of people called "the military."
And, yes, I'm oversimplifying to an extent that will make angels weep. But what it lets me do is treat police and military equally, which in a world with an increased mercenary presense, is (IMO) likely to be true. To-may-to, to-mah-to. It's all still berries used in delightful Italian dishes.
You want soldiers for hire to be much more prevelent in your society. That's not as hard as it sounds. Remember, a government's ability to impose order comes from its ability to threaten violence. No threat, no order.
No money, no threat.
Reduce your governments, no matter what kind they are, to the funding level of a large corporation and your problem is solved — because the government would no longer have the ability to organize, equip, and field a military that would keep vigilantism mercenaryship at bay.
This opens to doors to a whole lot of interesting things. Corporations (which today in the real world hire soldiers of fortune private military companies) would need to protect their national and international interestes — and they're suddenly on-par with even the local government to do so. The interest of a corporation is the bottom line, not usually a political ideology. Larger cities and/or towns would be similar, but their focus would be more "protection of resources" than a nation's would be (IMO). I say this because the larger the organization, the more that organization's focus is the preservation of its own power and not the promotion of a particular issue. (But, to be fair, I may be really, really optimistic with that statement.)
So, when you're talking about soldiers of fortune, it's all about the money, honey. And you need to have it to hire them. They may work occasionally for food or new equipment, but I believe that would be the exception and not the rule. But so long as a more powerful military and/or police force is unable to stop the mercenaries, your political landscape will remain... complicated.
NOTE: You need to understand that by equaling the field with the use of mercenaries, what you've done is make everything a government. The three kids who run the local Lord of the Rings fan club are a "government," they just don't have the resources to threaten enough violence to impose any more order than throwing little billy out of the treehouse. In other words, your world isn't really any different from today's world — your just calling some governments "corporations" and other governments "outlaw nations" and yet others "The Town of Wichita." In fact, given how much violence the world (and notably the U.S.) has seen in the last two years, your world might not end up looking a whole lot different from the real world. :-)
Having said that, the precense of mercenaries is IMO easy to justify. What's a bit more complicated is writing in the ethics and morals. How does a corporation stop their PMCs from killing everyone in a small sub-African village? Does it matter if the stock doesn't drop? Would the ability for the PMCs to march in a victory parade in the walled town's refounding day matter? I think that's what will be more fun: figuring out how to control what has, in many ways, proven to be uncontrollable, and thereby bring greater chaos.