But what happens when all of that storytelling fear turns into a lich firing a pea-shooter that just annoys people? I just don't see the lich as written being very exciting in combat and a creature that isn't exciting in combat is going to be a let-down when you try to explain his great power.
Well, there are two separate wants here, and you have to think of them separately to get the right answer:
1. The lich is personally capable of backing up that storytelling fear, even if you strip him down to his bony behind, lock him in a big room, and let the fully equipped and prepped party take him on. By definition, I think, this lich is a lot more powerful than the characters. Add some templates, or class levels, or just make up an uberlich, but if you want the guy to display great power, give him great power.
2. The lich, by virtue of his intelligence, undeadness, history of being cunning, whatever you think makes him scary--tends to have edges. It might be minions. It might be having 37 ways out, after hurting the party for 2 rounds. It might be some special equipment or environment that he is better positioned than the PCs to take advantage of. If the DM can pull it off, he might simply demonstrate more tactical ability than the average monster. It might be that he is simply the kind of devious mastermind that the party will never encounter while they are close to full strength (absent some truly inspired play by the players). If you want the guy to be scary without extra power, then you use all the scary tricks you can cram down your voluminous DM sleeves.
Of course, having thought of these things separately, nothing stops you from combining some subset of each into some truly frightening, synergistic hybrid lich.
What scares players is strange, anyway. Sometimes, the best thing to do is just try a bunch of things and see what they react to. Remember those things, and have the lich use some of them.
I had a campaign (Arcana Evolved), where in a crucial battle with a re-emergent crocodile godling, and his cultist followers, a summoned fire monkey (elemental) got loose among rolling barrels which turned out to contain lamp oil. Now part of the scariness was that they were trying to rescue some kidnapped villagers. But they were pretty scarred about flammable things for the rest of the campaign. And the fire monkey was on
their side.
Things spiraling out of control is almost as scary as the unknown. Unknown things spiraling out of control is really scary. You just need enough elements in the fight scene to get that spiral started.