Hopefully this isn't thread necromancy. Since "no failure state" is one of the central ideas of the game, I'd like to suggest a consequence that's more for drama than in-game punishment. I like the idea that the overlord actually is a danger to the continent, and would destroy it if left unchecked. I think it would be fun to have an option available at the start of the game that gives it some teeth, adding a countdown to the lifetime of the continent. Killing a lieutenant would extend the deadline, and maybe there would be some kind of dispatch mission to delay the overlord's evil plan as well.
But the big sticking point seems to be the penalty, making it something you notice but not end the game completely. I suggest forcing you and the other survivors to move to the next continent. The second continent is the same level as the one you left, and the old survivors are at the new settlement in addition to the new ones (but with the usual penalty for having to leave their home.) And a new countdown begins. I think this idea would be better if killing an overlord gave you some unique kind of gift that couldn't be had any other way, but the general idea might have merit on its own too. What do you guys think?