Random Undead

I think that making undead fit neatly into 'categories' goes a long way to make them not-scary and yes-boring in terms of encounters. My 'fix' was making every undead a semi-random horrible monstrosity that instills the dread of the unknown.

When generating a random undead, I roll 2d6, with 6s causing another die to be rolled, then divide the final sum by 2 to determine HD, rounding down or up depending on my whim. Fire kills them because fire is magic and burns the evil out of them, not because you can realistically incinerate human flesh so easily, and physical damage kills them because you cut them to pieces. Piercing attacks and blunt attacks do half damage, though against skeletal creatures blunt attacks are fully effective. Cold attacks are effective because the dead tend to be colder than living targets and can be more easily frozen and shattered, even if they won't die of hypothermia.

The Lesser Dead- Gross and hard to kill, but ultimately nothing more than a bunch of creatively murderous physical meat. Up to 4HD.
HD-in-6 chance of human-tier intelligence, otherwise as a rabid animal at best and a mindless murder-husk at worse. 1dHD ghastly powers.

1. Rib cage functions as giant maw. Auto-hitting bite for 1d6 in grapples.
2. Intestines function as whip/tentacle with 20 foot range.
3. Tibia/Ulna function as retractable bone shanks for legs/arms respectively. +4 to hit via surprise the first time they are used.
4. Flesh is green and putrescent. Save v disease on hit. Explodes in wave of pestilence when slain.
5. Tough, mummified, jerky-like flesh, or bloated and corpulent rolls of fat. +2 AC.
6. Crawling hands scuttle like spiders.
7. Spine turns head into extra flail-type attack.
8. Cannibal Integration- devouring body parts adds them to the undead's form, though supernatural abilities are lost.
9. Vomits liquids down nose and into mouth, save or drown each round after the first
10.  Has some vile fungus growing on it. Yellow Mold, Shriekers, whatever.
11. Has some vile insects infesting it- rot grubs, killer bees, a big centipede...
12. Nothing To Lose- AC as unarmored, extra +5 to hit people who have hit it that round. It'll slide down your sword to eat your face.
13. Muscle Slugs- upon "death," muscles crawl free as a swarm of bloodsucking leechlike undead
14. Skeleton- upon "death," bones reassemble into skeletal version, leaving meat behind.
15. Gore- upon "death" viscera and blood become crawling undead ooze that smothers and crawls 
16. Skinless, flayed, bloody. Skin functions as fragile glider of 1HD and a smothering attack, or +1AC while worn. Skin persists after death of main creature.
17. Can bend iron bars, smash through crypt doors, etc, at the cost of 1d4HP as the flesh is deformed by unnatural strength unless Greater Dead
18. Moves at a dead sprint, as unarmored run speed, even if armored. -1d4HP per round of high speed due to body falling apart, unless Greater Dead
19. Undying- HP damage cannot kill this creature, though it is considered immobile at 0HP. 
20. Spits teeth as sling bullets with 50' range. Collects new teeth from victims.

The Greater Dead- Eyes glow. Power on par with typical vampires, ghosts, and other horrible beings. Most create spawn if they kill someone in a particular way. Greater Dead have a HD-in-20 chance of being known to the church or other organizations likely to really dislike the undead. They are all intelligent.
+1 Greater power per 2 HD past 3, in addition to 1d6 lesser powers.

1. Echoes of Death- Can enforce mode of its first death upon people if they fail a save. Examples- Force wings to fail and ropes to snap for death by falling, cause flammable objects carried to ignite for death by fire, cause wounds to bleed without end (-1HP per hit), freeze people, spread plague etc etc. Needs line of sight.
2.  Can turn invisible.
3.  Eye contact or a bite or (gruesome delivery method) causes the living to fly into a berserk fury, unable to tell friend from foe but wishing to slay all, then themselves.
4. Melee attacks also drain damage*10 (or 100, or even 1000, or just a level) XP. Alive with fairy fire.
5. Being within 5' forces a saving throw each round, or 1d10 year of aging. Looks incredibly aged.
6. This creature will return from death in a few months or years regardless of how it is killed, unless its spirit is sought out in the underworld and stopped at the source.
7. Flies around like a meatpuppet on strings.
8.  Alternate swarmform of burning cremation ash, grave dust, swarm of worms, etc
9.  Those in its presence lose 1HP per round, and it heals HP lost this way. Mouth appears to be sucking in light and life, a black moaning pit.
10. Reaper's Tools- Cannot be harmed by weapons. 'impromptu' weapons like rocks and shovels work, axes and swords and fists do not.
11. Mortal beings save or be paralyzed with fear upon viewing the creature for 1d6 rounds. Hirelings check morale each round.
12.  Vampiric, heals self equal to damage dealt with its overgrown fangs.
13. Those damaging it take equal damage themselves. Appears as a dead version of whoever looks at it.
14. Has learned terrible secrets of death. As spellcaster of equivalent level.
15. Can masquerade as a living creature.
16. Doesn't need eyes to see, can detect life within 60 feet.
17. Fossilized- 20 AC. At least 10,000 years old.
18. Ghostly form, passes through physical objects and immune to most forms of attack.
19. Melee attacks force a save or your spirit is knocked out of your body, If struck in spirit form, save or have your soul eaten, body can be coup de graced if no one interrupts. Can repossess your body to come back to life, or someone elses body if it's missing a soul or can be healed of whatever killed that body.
20. On max damage hits, takes off limb which transforms into 1HD monster. Crawling hand, gut snake, etc. Reattaches to the Dead in 1d6 rounds, returning HP, if not destroyed. Applies to own limbs and other people's.

Weaknesses

1. Powerless in sunlight/dormant during day
2. Whatever killed it in life forces a save or die when applied in death. 
3. Cannot set foot over holy grounds/houses/above its grave-level/ships/roads
4. Must check morale when faced with fire/salt/beans/water/silver/whatever, ignites as though it was oil soaked on contact
5. Blind.
6. Missing 1d4 limbs
7. Cannot harm one of- Women, Children, Dogs, Fools, Nobles, Priests
8. Pursued by psychopomps seeking to drag it back to hell, must constantly be on the move

Example Greater Dead
Skratti. 10HD. Fell while climbing into the Great Rot.

High move speed
20 foot attack range via haunted ropes
Infested with mold, save or lose a turn choking on spores striking it in melee. Has a rare and valuable mushroom growing on it.
Can command things to FALL AS I FELL, snapping ropes, ruining flight, crumbling footholds, etc on failed saves.
Uses climbing ropes to swing around like spiderman, can rise up on them to 'fly' up to 50 feet in the air
Can't see things further than 60 feet away