How about some of the folk from the Wyrmberg? What happened to Coin? As to Carcer - I'm sure he was executed.
Coin's in his bubble isn't he? I think it was a seperate dimension in a glass sphere or something like that...?
And I don't think he was not the Villain in that sense, it was more his father in the metal wand who gave him ideas.
EDIT: I thought of the wyrmberg people too, but they don't fit into the current stories and I'd like to avoid dragons... they're very, very, very, very difficult to draw.
As to other baddies:
Weeel... I've looked through the Discworld Companion in the meantime, but I didn't really find a candidate. Guess I'll have to do my own villain
(I'm not good at villains)