See, I'm in the camp where sometimes Villains (and even some encounters) should be insurmountable - that the Characters should have the common sense to "run away to fight another day" whereas some DM's believe that ALL encounters should be defeatable (is that even a word LoL) including Major Villains.
But, in my opinion at least - that's not very realistic, now is it.
There are plenty of heroic tales where the main protagonist(s) flee or have to return to complete a quest/defeat some evil (the Hobbits in the Lord of the Rings don't confront the Ring Wraiths for example, not until the have Aragorn with them - and the company flees into mines of Moria to escape the watcher in the water ) - if not at the very least the Hero in question prepares himself in some way to vanquish the evil (as in the legend of the Lambton Worm).
Unfortunately, the modern "trend" is balance over story telling - something I've never found particularly palatable when running (or even playing in) games.
A common thread in my own Games are the "Three Tiers of Villainy" as I like to call them, the different sorts of encounter a Party of Player Characters might encounter.
The Three Tiers of Villainy
Tier One - The most basic villain types, Minions, Monsters, and Morons. Those Low-Level (total number of levels/hit dice generally within two levels of the total Part Level) encounters that form the meat and potatoes of any game. These can be represented by a "spread" - as in 1 monster/minion/npc per party level, or as a "combined" encounter - eg 5 1st level PCs could encounter a 5 hit dice monster.
At the end of the day, even when designed to be a challenge to your players, they should be well-within your party's capability to deal with them.
Tier Two - The Bosses. This is the most challenging "encounter" a DM can put it, tough enough to (at least in theory) perform a total Party Wipe Out (if they are stupid enough to take such an encounter on) when initially encountered, but not unbeatable IN THE LONG RUN. These are the Baddies the PCs return to kill/exact revenge upon. The Long Term Villains that can make a campaign truly memorable. Of course, such "Bosses" CAN be taken on, and on rare occasions the PCs will get lucky (or the NPC unlucky with his saves etc) and defeat such a Tier Two Villain early on, if that's the case - let them gloat etc. Just have him (or her) replaced, and make sure the new Villain has an entourage with them this time!
To sum up, Tier Two Villains should be ALMOST unbeatable - but at the end of the Day they are there to entertain your Players, so don't be surprised when they do (eventually) get killed!
Tier Three - The Gods, Demon Princes, & Arch-Devils. Though such encounters will have attributes/statistics - they aren't in place for the PCs to fight. They are there rather for flavour, and to scare the "bejesus" out of your Players.
Evil Deities turning up to gloat (and tell the Party their plans of course), Demon Princes there to "slap them around" a bit, before you let them "find" a powerful magic item or two. Or an Arch-Devil, there to tempt them into "making a deal" (if you get me) - Tier Three encounters are there for one reason, and one reason only - the scare the crap out of your players.
DO NOT put such Villains/Monsters in as an standard encounter, at least some of your Players characters WILL die - and that's a fact.
So, even though I am not a fan of "balance" in the rule set (I find it a little too constraining myself) - I do believe in balance when it comes to telling a tale.
And telling a good story is what its all about for me as a DM.