Something I always figured I do if I made a zombie campaign is feature good all zombie-evolution. So while right now your characters might have a tough time with their zombies, eventually they will get to be powerful enough or fortified enough that zombies cease to be scary. Therefore, there are rarer more powerful versions of zombies that occasionally emerge.
Here's some examples. Zombies with magic, zombies that climb or leap, zombies that spit acid or poison etc. You could introduce these zombies from afar (so the PCs have time to kill it), but the real fear comes when this difficult to defeat zombie comes in multiples, or at night, or in an even more dangerous variety.