"They were discharged after the war, often as whole units."
This made me think... let's say a warlord has the basic smarts telling him discharging his bloodthirsty army in his brand new kingdom is not a good idea. So after the war, as the situation is calming down, he would try to slowly convert his units into regular troops, such as they are needed, put them into local militias, and release the soldiers one by one, rather than whole groups. As the more useful mercenaries would be employed or wander off to other assignments, remaining would be the brutal hard core, light on listening to orders but heavy into looting, raping and pillaging.
These would be sent onto a 'small, but profitable' attack or raid against a random enemy, one which accidentally ends in their slaughter. Oops. We kinda forgot that's where the elite troops were stationed.
Now that would be a nice story for the history books.