Continuing on my last post: Sometimes, the players aren't going to fail. Sometimes, you're going to go into a session with a plan for them to get within an inch of taking out the villain, and they go two feet past you and totally smoke the dude.
Because that happens. I want to make clear that my take-it-as-it-stands "advice" isn't meant as an endorsement of railroading. Sometimes what you, as the GM, are trying to do just isn't going to work.
However, there are a couple of strategies I've used in the past, to ensure maximal survival for my villains at crucial moments.
1. Have an exit strategy
Secret passage. Smoke bomb. Invisibility potion. Giant monster that comes crashing into the room. Something explodes. Whether it's something the villain plans, or something that I plan as an in-game coincidence, I'll sometimes put together a general purpose escape plan for when things turn south.
Of course there's a secret passageway there--the villain, being a genius, had one installed months ago. This is my favorite strategy. Very similar to the first strategy, but usually I can come up with better plans once I already know what my players are doing.
3. That was just my ramen!
Who says the villain the players just offed was really the major bad guy? This is actually something I've planned for ahead of time, but I can see it working just as well in a "Gee, now all my notes are totally useless" situation. It also provides a nice combination of success and failure, because while they did get to pound on someone, the real threat is still out there.