Gr, I had a great long rant and then Kernel32 crashed. So after repairing the FATs and stuff I'll try to replicate it here from memory.
Polymorph - WizarDru says it all.
Feeblemind - throw in a dragon for hire, funded by the villains. It's far too powerful for the PCs, and once it discovers this it flies off. But if you feeblemind it, why should it be interested in fair play any more? It's reduced to a mindless predator with fire breath. And the fighters will likely be the first insects in its way.
Spell resistance - throw in some formians or something. SR 21 on a taskmaster: your casters will only be able to affect it half the time, and it can take possession of their minds. Which would really suck for the rest of the party. A myrmach is SR 25, which requires a penetration roll of 15+ at your level, and it's got fast healing and teleporting... bad news all round, I think.
Ambush - surround the party with close ranks of weak monsters. Sure, you could fireball them all - but you'd be at the epicenter.
People who retreat to outer planes should realise that those planes are home to the biggest, baddest monsters in the multiverse. The astral plane may be timeless, but a gang of rampaging githisomethings is sure to cause a little bit of astrophobia.
And time management should be in the DM's hands. If the players retreat to recuperate, the villains kill the hostages - it's as simple as that.
What you really need is a horde of spell-resistant flying monsters. Vrock demons are a little too fierce for that just yet, unless you really want to...
A group of vampire adventurers is a good idea. Because they're evil, the cleric can only spont inflict spells, which heal undead and harm anything else - a good bargain.
Finally, teleport has its flaws. A decent villain will have Screen spells up all around his fortress, giving the PCs a completely erroneous image of his sanctum, so when they try to teleport there... they mishap and end up in a 'similar location'. This works best when the 'similar location' is in an underwater city and is laced with dimensional anchors, or something similar.
(Plus, teleporting isn't the best for long-distance group travel unless you've got lots of Reduce spells memorised. It's quite ridiculous to 'port into a throneroom and dislodge these three-foot midgets with greatswords from your robes. Weight restrictions are your friend.)