I was reading this thread and I kept thinking, "Lex Luthor". What would Lex Luthor do. This guy gives Superman a run for his money every day. So what you need is a genius. A mastermind villain would make an excellent, and very much recurring, threat to your PCs and the best way to keep him from being killed outright, make him loved. Make his people love him and follow him blindly. It would be a great dilemma to have this seemingly evil man who is hellbent on taking over what's left of humanity actually be a really good leader. His people are happy, well cared for and he's bringing back things like art and education. He is also a facist pig. Anyone who speaks out against him disappears in the night, any settlement who refuses to join him is sacked. To his people the disappearances are "rumors" or "unrelated". The burned villages were "threats" to their way of life and had "weapons of mass destruction" hidden in them. The PCs cannot convince these people to rebel against or abandon their leader. If the heroes exile/imprison him they will find/free him. If they kill him outright, they are taking an entire (City? Nation?) people's way of life away and will most likely make the mastermind villain a martyr to his people. This is basically an extension of the warlord idea, but bringing to the level worthy of a super human response lasting longer than one session. The Mastermind could attempt to recruit the heroes into his army. Or if they are a village's protector, the Mastermind could try to acquire the village.