I remember that I wanted this functionality in Heroes V, but it was not to be. So here is my suggestion for Elemental.
I would like the possibility to hire mercenaries to bother my enemies so that I would not have to go to full war every time I wish to punish someone. Mercenaries would act like other roaming monsters only that they would target a set kingdom. This could be a random event (a group of mercenaries offer their services) or a more standard functionality if you build a special building which would allow hireing.
The size of the army hired would vary a bit by random, but mostly by how much you pay them.
There would ofcourse be some balancing issues here. Things like size of hired army, price of hireing, how often you can hire mercenaries and so on.
As a final thought. If a group of mercenaries kills the last city of a kingdom they would start an empire of their own based on this city.