Just remember that there will always be those who will not compromise with evil for any reason, no matter how "lesser" they seem. Create a band of fanatics of some Lawful Good God of Light. They are not swayed by the acceptance of these evil beings have have broken from their temple/tradition because they consider it "corrupt and in violation of the True Law." Clerics, Paladins, and LG Rangers all determined to wipe undead from the face of the world. Perhaps they even believe if they succeed, or even try really hard, their god will manifest and save them all from the Big Evil the party is facing. This would be a perfect challenging counter to your evil party, and they would show up again and again with weapons, spells, feats, and class abilities all centered around fighting undead.
On the other hand, if you are worried about their immunities throw things at them that are just as tough. A sentient iron golem (the housing for some angelic general trapped within?) with a sorcerer companion who does nothing but cast fire spells centerd on the golem, or some similar on going fire effects would be tough to beat. Like Shin said, there are all kinds of powerful foes that might be aligned with good or evil to oppose the party.