I don't know Rappan Athuk, but I did finish running a group through RttToEE, and found myself with some of the problems you've mentioned.
Teleporting in and out was something of a problem, but I cut down on it a bit by looking up the weight limits on the teleport spell, and had the players add up how much their "Loaded for Bear" characters weighed. Turns out that one of the party would have to stay behind each time, a problem not helped by their cunning plan to keep the monk polymorphed into a troll all the time for the awesome stats. (Stupid 3.0 Polymorph...) This was somewhat solved by Polymorphing a party member into a snake for encumbrance purposes, but there goes another high level spell, and this sort of arrangement isn't practical in a combat situation. Also, you can only teleport people you can touch, right? Walls cut down on touching. Cast Wall of ... in combat for laughs. More on that later.
I didn't have too much trouble with scrying, fortunately. I think it is wholly reasonable, though, to have goodly sections of a high level dungeon lead-shielded or otherwise scry-proof. (especially personal quarters and war rooms.) Especially if the resident bad guys are magic savvy like the RttToEE gang were. Heck, even making most of the dungeons "hot areas" teleport proof and ethereal proof would be very reasonable, as at high levels Not doing so would be like leaving the screen door open on the nuclear sub. I just figure that the high level baddies don't especially like walking either, and a certain portion of any area will be "teleport open" for their use also. Of course, these areas would be as guarded or trapped as the front door.
If the PCs used a lot of buff-scry-teleport, I don't see why the bad guys wouldn't, too. Getting a party description from some surviving minion, bad guy scrys them at their nocturnal resting place, assembles strike team, 'ports in, dumps a one-round salvo into sentry/campsite, and one bad guy of strike team has a readied teleport home. Works good with sneak attacks vs. single sentry (heaven help 'em if he goes down...) or a fireball into the campsite. Cloudkill for your tunnelling campers would be more fun for you than your players, and is minimal risk for your villain. Just make them need more healing spells, and give them less time to get spells. This speeds players up like no ticking clock ever seems to. Oh, and your players will love to hate the guys responsible for this. If your players come up with a solution, steal it for the bad guys. They can't complain if the baddies see them doing it.
The other thing players love to hate in combat are environment/obstacle challenges. Consider a mephit, air elemental, or something else small and maneuverable with silence and invisibility cast on it, whose orders are to stay out of the way in combat, not attack, but to stay near a spell caster. Or a demon, who can see in magical darkness, and use darkness at will. At will! How many layered darkness spells would this creature have going at one time in the spot where it would prefer to fight the PCs? Sure, a light spell can cancel one, but that's only one. Area dispels are better, but that could be a lot of rolls, and they'll still fail one, right? Plus, that's one less spell to do something else with. The mist and fog spells are low level, but cut down on those blast spells from afar. If the PC's can't see, move the combat action from the battlemat to behind the screen. And walls. Doesn't matter what kind. Ice, fire, stone, steel, force. If you can cut the party in half, a weenie fight can become serious. If you can't touch the cleric, and he can't touch you, see how cocky you are against even moderate foes. Hell, done right, you can even wind up with the wizard or other soft target in melee, which is an eye opener.
Oh, nuts. I'm really not this longwinded in real life. This is just more fun than work, is all. Anyhoo, don't go too heavy on some of these ploys, just enough to challenge 'em, not piss 'em off. You'll know you've done right when they start to steal your ideas. Nobody used enveloping mist until I screwed 'em with it.