Movies and TV shows do this trick all the time: The villian is "killed" but somehow returns next sequel or episode. Players won't mind the villain coming back, they just like to have the satisfaction of kicking his butt.
Try to have the fight take place in a memorable, hazardous, environment. Have the npc "die" by being reduced to zero hit points, give the players the full satisfaction of beating him during the combat encounter. Describe how he collapses, bleeding from his wounds, maybe gasps some final words. Then describe how he is somehow killed EVEN MORE by the environment:
1.) The magic castle collapses all around him, the party has to rush out or they are buried, or as the castle collapses the villain's body falls through one of the many ever expanding cracks.
2.) The villain falls off the cliff, rope bridge, rooftop, cloudship, etc.
3.) The villain is sucked into a boiling pit of mud, lava, etc.
4.) Buried in an avalanche
5.) Some player destroys a rope or pulls a switch, and a rope around npc's leg wraps around him and drags him off to some gruesome fate
6.) Knocked into a mine cart that goes careering off into darkness.
7.) The blow that knocks him to zero hitpoints breaks his concentration and the spirits, monsters, magic, etc. he was using against the party or attempting to harness turns against him and carries him off screaming.
Bonus points if the player is actually able to use a combat power that accomplishes this (using a push to knock him off the edge, into a gnomish food processor, etc). Anyhow give him a brutal, punishing, fate over and on top of whatever attack the players did to drop him to zero hp. The trick is, whatever fate happens, doesn't involve recovering the body.
So of course the villain returns from certain death. Be sure to give him a prominent scar associated with how he was defeated last time. It doesn't matter how he returns he just does. Just like every villian from tv shows and movies manages to.
Be sure the next time to make his death even more outrageous. When one player inevitably mentions that he is probably not dead, reply "Surely no one could have survived [insert gruesome fate]. He's gone for good this time." Dramatic pause. "Or is he?"
Eventually let the players kill him. Then bring him back all over again as an undead villain.