Invert the "bad-lich-turns-out-to-be-good" idea: A really sinister lich would probably love to have people convinced that he's just a kindly, helpful old gent. Suppose one such lich has been working hard on his image for a century or two...he saves people from natural disasters (which he created himself), gives out magical gifts (which are cursed in some nonobvious way), kisses babies, the whole shebang. The players come to suspect him of actually being evil ("Hey...two centuries old? That's before Second Edition came out! He must be evil!") and have to stop him. But first, they have to convince the locals, who love the old guy, that they've been wrong about him all this time. ("Gandalf? The old coot with the fireworks? Evil? Get outta here.")