As requested by Zak's Magic RPG 8-Ball.
1. SIDEWAYS IN TIME - Always reincarnates into new form d6 turns after death. Perhaps a Time Lord can assist in cleaning this mess up?
2. ALREADY DEAD - Not a lich, this S.O.B. actually clawed his way back from UltraHades. Will have to be escorted back to the realm of the dead and incarcerated in Hellking Plutodaemon's Black Adamantine Prison. But will the Hellking let the PCs back out?
3. DOOMBOTS - The real villain is safely in his lair in the middle of their own personal postage stamp country, somewhere across the ocean.
4. HYPERDIMENSIONAL BODY - What the PCs see is simply the 3-D limb of some fourth or higher dimensional jerkwad. The 3D body has no vital organs in it. Perhaps True Seeing or Etherealness can help find a stabbable hyperspleen lurking in N-space.
5. EVIL VIRUS - As villain dies they cough up blood on nearest PC, who becomes the new villain after 2-3 days of flulike symptoms.
6. TRANSGENDER NAZGULISM - Prophecy says villain can be killed by neither males nor females.
7. THAT KRISHNA IS SUCH A CUT-UP - Villain is actually some high-ranking cosmic being trying to teach one of the PCs some obscure point about karma or honor or the circle of life or some crap like that.
8. SOME CRAZY POMO META STUPIDITY - Villain removes mask to reveal he is a fictional character from some novel. PCs will be unable to kill the villain until they come to terms with their own fictionality.
9. SERIOUS X-MEN SERIOUSNESS - Villain is secretly one of the PC's ancestors, brought to the present by giant time-travelling robots or something. Kill the villain and the PC ceases to exist, totally wrecking the whole dang campaign world.
10. ACHILLES' JAZZ - Only a critical strike to one secret place will actually hurt this dillweed. You ever see the kung fu movie Invincible Armor? The villain could use his kung fu to pull something similar and actually chose to leave his nutsack vulnerable. That did not end well.
11. ME AND MY VILLAIN - The villain is actually the shadow of the beardy old wizard or whatever that sent the PCs on this crazy mission seven sessions back. Maybe they will need to figure out a way to sharpen the shadows of their swords, create spells like shadowball and shadow missile, etc.
12. AWWWWW - Villain is secretly a cute little puppy.