- teleportation and scrying are already limited; and,
- going beyond the built-in limitations really needs to mesh with the individual setting.
(My LBBs are still in storage, so I'm going by the AD&D 1e PHB. Also, I'm leaving out Drawmij's Instant Summons, Vanish, and the clerical Word of Recall for now.)
Blink is rather minor, really only providing a temporary combat advantage; it seems petty to ban Blink, although the flat bans on teleportation should also ban Blink. Dimension Door and Teleport are the real intended victims of such bans, since they are the travel-oriented spells.
Dimension Door requires a clear vision of the destination; the meaning of "clear vision" is debatable, although Teleport does include some guidelines: I'd suggest that only a place currently being seen from a distance, very familiar, or studied carefully counts as a clear vision, whereas scrying is either "viewed once" or "seen casually" at best. Dimension Door has a range limit and an element of the unknown: the MU does not know if a destination currently not being viewed has changed, risking the chance that the location is currently physically occupied. Even small objects prevent arrival at the destination and in fact traps the teleporter on another plane. So, an NPC villain's best protection against Dimension Door is keeping objects moving through the space randomly. Particles of dust shouldn't count, and the spell description specifies a solid body rather than a liquid or dense gas, but even a few slowly-swinging pendulums, perpetually-bouncing balls, or a regular patrol could introduce a risk.
Teleport is a stronger spell, allowing crossing nearly any distance, but it is also more dangerous; there is always a possibility of error, coming in too high and falling, possibly to one's death, or too low, which almost certainly means death -- there is no "being trapped on the Astral Plane" for Teleport. This part bears re-emphasizing: "there is no possibility of teleporting to an area of empty space, is. a substantial area of surface must be there". Again, simply having floors that move up and down a few feet can screw up a Teleport spell, perhaps fatally. Occasionally casting Guards and Wards should keep at least the stair cases risky as Dimension Door or Teleport destinations.
Note also that neither spell allows passage to another plane. So, the simple solution for a high-level NPC is to store important stuff on a different plane than the main headquarters. A wizard's tower with some kind of permanent gate to the ethereal counterpart of the tower would provide good security.
I'm not going to go through all the divination spells, but I want to consider crystal balls and the Clairvoyance, Contact Other Plane, and Legend Lore spells. The Clairvoyance description specifically states it can only be used to peer into well-known areas or obvious areas ("behind that door" or "the other side of that hill".) So, it should follow some of the same restrictions as Dimension Door -- you can't scry into a place you haven't seen before unless it fits the "obvious" criteria. It shouldn't be a big deal to an NPC villain: by the time the party can use Clairvoyance to find the NPC's location, they've already broken into HQ. Note, though, that the description specifies that the spell is blocked by metal and also by "magical protections," which might include Protection From Evil, depending on how you interpret the protection against enchanted creatures it provides. Does scrying with hostile intent count? I'd let it; others may disagree.
Contact Other Plane is a risky way to get yes-or-no answers. It does not allow visions of other areas, so it's useless for establishing Teleport destinations. The only danger, then, is to short-circuiting the plot; I think I made myself clear in the previous post how I feel about the plot. Besides, unless they are very good guessers, Contact Other Plane will narrow down a search, but not really short-circuit the adventure.
Legend Lore likewise isn't visual, and is in fact cryptic; most NPC villains are going to be mere rumors, and some might not be legendary, limiting the usefulness of this spell.
A crystal ball, on the other hand, is typically interpreted as a magic item that casts Clairvoyance or Wizard Eye, but with extra effectiveness: you can locate known targets. But there's also a listed chance of failure and the possibility of insanity, at least in the AD&D write-up in the DMG. I'm thinking I'd run it like a Clairvoyance spell teamed with Contact Other Plane or Legend Lore: you ask a question, it shows you visual answers. If your question is "where is Villain X?" (or Quest Object Y,) it will show you a sequence of images detailing the route or steps needed to locate it -- which means that it may cut off before it shows you the complete route, or may drive you insane if you follow the route too long.
Again, I'm tempted to allow a Protection From Evil to block a crystal ball, making it a good temporary scry guard. Plus, being on another plane reduces the chances of being located by scrying, by the book. Since normal Clairvoyance fails when the location is on another plane, the ethereal portal solution mentioned for teleportation may be a good foil for scrying.
There's also Dispel Magic and Darkness, both specifically mentioned in the AD&D DMG (p. 119) as a foil to scrying. It seems better to let NPCs stop scrying dynamically rather than ban it outright.
More discussion in another post.