Hm, I mean the A4 has pretty robust social services right? I think if politicians riding on a platform of Tax Cuts where elected in any of the A4 countries they'd sooner go for the welfare systems rather than the military, sort of like a lot of neocons. At least I can't see them wanting to downsize too much militarily; those orbital bombardment platforms are flashy, cool, and "cleaner" than nukes, and unless I'm mistaken those things are a huge reason the A4 have so much power to begin with.
On a semi-related note, I think there is one clear weakpoint for the A4 that they haven't had a chance to deal with in depth the way we have OTL, and that would be decentralized, international terrorism. Let's say some Germans get together and did ITTL's version of 9/11 in revenge for Stettin; the A4 could destroy the terror cell for sure, but what happens if a new one crops up independently? It would be the same kind of whack-a-mole game the OTL US has been playing in the Mideast for the past two decades or so. Just spitballing here, but if the A4 got into a quagmire conflicts like OTL's Vietnam or Iraq Wars, that'd probably do more damage to their roles as global policeman than anything else.
There have been movements in most of the A4 countries to greatly reduce taxes, even some efforts to get the various countries to simply stop the near constant "wartime mentality". They have, to some degree, worked in that tax rates have been lowered across the A4 from post war highs. One of the issues related to trying to cut "just" social services or military spending is that the two are far more closely related than IOTL. Transport is underwritten because it is all dual use, same goes for energy, food prices for staples have both floors and ceilings (think the U.S. and dairy prices in the 70s & 80s) to control military spending and ensure supply, and Universal health care is, at least in part, seen as a way to ensure population that can handle crisis (at least that is what the A4 tells itself as a justification, self justification is not limited to OTL). What really allows the current set-up to function is that the tax structure, much as was the case in the U.S. prior to the 1980's, prevents massive wage disparity. There are wealthy people, and there are poor people, but there is not the sort of scenario as exists today (Jeff Bezos would be a billionaire in the ATL U.S., might even touch 11 figures in a really good year, but would never see 12 figures). Obviously the really wealthy would like to see that change, the poor would like to see more social spending than a Mars mission. so far they have both been somewhat frustrated.
Terrorism is always a difficult issue. It is, however, much less difficult to deal with if you use the "Alfred in Batman" method. In one of the movies he talks about when he and some of his friends (i.e. SAS) were trying to chase down a terrorist/criminal who was using the forest for cover. When Bruce asks how the stopped him Alfred's reply is "We burned down the forest." The A4 and its allies, especially the Poles and Russians, (the Vietnamese and Philippine SPECOPS units are also not to be trifled with) are a good deal less worried about breaking a few eggs than IOTL. The A4 sees terrorist and thinks "Werewolves" (i.e. Waffen SS stay behinds). Really bad thing for the A4 to think "Werewolves", especially in Germany.
It is important to keep in mind that although the A4 countries look a lot like mirror of OTL's countries, they very much are not. The A4 leadership (and citizens) would see it as being more pragmatic, from OTL's perspective is is closer to callous. You use a stick, they use a gun; use a knife and they use artillery. The A4 really doesn't interfere much in internal policies for foreign countries short of genocide or aggressive international war, in those cases they just end the problem, generally by ending those involved, pick up their toys and leave.
The exception is Germany; there, to this day, there are "peacekeepers" largely drawn from populations that have a LOT of reasons to be less than friendly to the German people (even a couple generations after the War). Those forces are thoroughly professional, rigidly disciplined, and rather make Roman Legions look like Cub Scouts. Terrorists always require some support, both from the local population and usually from outside, at least economically. The population of the German statelets are unwilling (or too scared, take your pick) to provide support to terrorists, especially since the various statelets are actually fairly pleasant place to live, outside of the damage remaining from the war (good social services, especially medical care, low unemployment, reasonable wages) making "the sea" terrorists need to hide in very shallow. There is also virtually zero economic support from outside. The USSR tries to stir things up, but Communism is almost as discredited as Fascism politically, and the country doesn't have two rubles to rub together, the Chinese had a go at starting trouble conventionally and in both cases were stopped cold, so they have also abandoned the effort. India is a competitor to the A4, not an opponent, so there is no funding there either.
Terrorists in the German statelets are more or less criminal gangs and both the authorities and the population treats them as such.