Well, a couple campaigns back, we were faced with the whole Buff-Scry-Teleport combo, and we came close to removing the teleport spells altogether. But in the end, what we did instead was create a bunch of custom spells dealing with this sort of thing. They all fit into the world just fine, because there was an organization in-game that was exactly the kind of people that'd be researching this stuff to begin with.
There was a 2nd/3rd-level spell that scrambled scrying, forcing the scryer to make spot/listen checks to draw any information from a 5' area around one target. (Duration was 1 hour/level, so even though it doesn't sound like much of an effect, it made scrying just unreliable enough that people stopped depending on it.)
There was an AoE dimensional anchor. There were scry trap spells, scry detection spells, teleport redirection spells, and triggered area dispels (really handy vs buffs). Plus items for quite a few of these, of course.
And then at one point, the PCs met the guy who had actually researched all of these spells, and found out he had also made a really nasty 9th-level custom spell called reality anchor that shut down all teleportation, scrying, summoning, planar travel, etc. within 60' of the caster. It also tried to banish any outsiders within the area, if the caster spent a round concentrating. The best part was that you wouldn't know it was there until you tried something, at which point it'd not only interrupt, it'd deal 1d6 damage per spell level.
Anyway, you don't need to design custom spells, really; just realize that the splatbooks and such are loaded with spells or items designed to counteract many of the PHB spells. So, all the DM needs to do is throw a few of those into the campaign.