How about said group of outmatched paladins are ambushed and raised as zombie lords?
The BBEG loves heroes/strong hostiles as minions.
I was planning a similar sub-antagonist, except it's not a lich.
It was based on a comic i read once, where there were these special weapons with unique properties. The blade wielded by a psycho-girl had the power to animate the dead as, in PF terms, zombie lords. She had killed heroes and generals, the two greatest had served as her bodyguard/favorite "combat puppets".
Er..not so much. Their bodies didn't decay for starters, they were preserved.
The psycho-girl killed and raised/enslaved a sentient gorilla chieftain, an expert marksman general, a twf female hero and sent them as combatants against the protagonists. All while taunting them like the utterly insane b!tch she is. :)
Quite demoralizing to realize you could end up that way too.
Maybe the paladins were investigating the merchant prince too or one of them is his brother, so the party has to speak to them, but their adventure finds them coming across the scene of a recent scuffle. Aside from the broken corpse of one of the paladins they've been tracking down to find, there's a scrap of paper about a meeting with...*torn paper obscures the name." Now the PCs need to try to save the Paladins before they're turned/eaten/have a bad day to find out their next source of intel on this wayward prince.
The party MAY be able to save some of the paladin's securing the intel, or they may be too late, and encounter the lich with his newly recruited cohorts of anti-paladins, zombie lords, etc...
Then the plot can go from there, maybe the prince and lich are in cahoots, or maybe the prince stole something from the lich and the lich could try suggesting they work together, now your party has a new hook and ally. After all, I doubt most polite society would appreciate shadows and wights strolling into town asking questions.
After the investigation, they find out the lich was the prince, or that the prince and lich were working together all along and the lich was just sending the party on a wild goose chase. Or maybe the prince is locked way in the bowels of the city for some nefarious purpose, etc... it could go many directions.
...hunt for a merchant prince whose organization has been trying to kill them. The new large kingdom city they are entering will be run by a Lich, and terrorized by his Spectre guards. Can you think of any twists and turns that might make for good adventuring?
In a linear thread, the organization will have some connection or rivalry with the Lich ruler. Very much expected. As are a cadre of paladins to make up for the group's shortcomings.
Surprises are always good. The surprise is that the lich really isn't bad. But everything the players hear about him is totally evil. The group (captured by the spectral guards after being teased by the GM that they may be able to sneak by) is brought before the Lich. The Lich could have a reputation for ruling harshly, but he is really a misunderstood villain. W/O knowing the rest of the group, perhaps the druid has some connection in the past (A last name, an origin, etc...) that the Lich recognizes and needs help in laying something to rest that has haunted him for 200 years. The lich really doesn't "want" to be bad, but is under some tragic, cursed obligation.