An incarnation of Laserbeak, and condor/cyborgs for the Cosmic Era
Do not meddle in the affairs of wizards... -- Gildor, via J R R Tolkien
The first sign of the Army of the Lost are the legs. Blown off legs, hopping along wearing their military boots. And not long afterwards, the rest of the Army arrives, and the horizon from left to right is filled with the decomposing bodies, many of which carry weapons. Unless you can outrun them or fortify your position, you will soon be joining this army of the Undead.
The local band of 'nasties' (goblins / orcs / whatever) lives in relative peace with the local population.
Along come the PCs and go through their usual heroic monster bashing routine, wiping out the nasties and pinching all their stuff, then continue on their way.
Problem is, they don't kill ALL he nasties. The survivors want revenge and, after spending a few months recovering, start to take it in their own inimitable style (which is not unlike that of the PCs come to think of it).
Next time the PCs are in the area they find themselves VERY unpopular with the townsfolk.