This became a problem in my last Dark Sun campaign that just ended. (The PCs did it several times to NPCs and the NPCs returned the favor to them.) One of the cheap solutions I came up with is that nothing in the teleport description says that the spell displaces matter in the way of the incoming teleport.
Eventually the PCs started running into NPCs who filled the room with streamers hanging from the ceiling, or string strategically strung throughout the room. Sand and water work well if you are protecting something that you don't need to use often. Of course this doesn't work well in rooms that are in use. My NPCs also used "white noise" effects such as waterfalls to make hearing through clairaudience and scrying difficult.
I also borrowed the old 2e bit about heavy metals, thick stone and energy emissions blocking some divinations and teleportation and extended this to most divinations and all teleportation. My PCs were fine with this because it gave them simple cheap protection too.
Another solution I use in all of my campaigns is to attack the scry sensor. I ruled long ago that any spell that creates a magical sensor forms a conduit to your own senses opens you to attack through the sensor. (I remembered this from Planescape). The sensor is treated as an incorporeal magical construct that has 1hp per caster level. Any damage to the sensor translates to damage to the scry focus device and to the caster.
Before I started my current Rokugan campaign I also made some house-rule changes to teleport by limiting its range to 5 miles per caster level (10 miles for Teleport without Error and Teleport Circle). Additionally, I changed all scry and clairvoyance and locater type spells with formerly unlimited range to 5 miles per caster level (Greater scrying and Discern Location are 10 miles per level).
Another trick that works well is to without limiting teleportation too much make teleport work Star Trek-style in that the re-matierialization is slow (i.e. a full-round to materialize.) This makes it dangerous to pop-in on someone because they have time to strike you flat-footed before you are fully phased-in.
Lastly, I used and created a small host of spells and magic items in my old campaigns that protected against teleportation. (Allowing attacks on the scry sensor proved to be more than sufficient protection against scrying.)
1. Dimensional wards: (Magic Item) you need a minimum of three of these wondrous items to form a bounded space. Once activated, dimensional travel into, out of, or within that space is impossible. The wards can be de-activated at a touch, moved, and re-activated again if the owner chooses. I also have a 5th lvl spell of the same name and effects that lasts 1 day per level. (This was my comversion of a 2e planescape item.)
2. Teleport Scramble
5th lvl spell) This ward causes all incoming teleportation effects to behave as a teleport spell with the worst possible result (i.e. as if teleporting to a place that doesn't exist.) It lasts a day per caster level.
3. Redirect Teleport: (6th lvl spell) This ward allows the caster to set the arrival location and orientation of any incoming teleport effect. The location and orientation is set when the spell is cast and cannot be changed. The spell lasts a day per level. (Bad guys in my campaign set the arrival point inside a trapped room, a magma chamber a dungeon or simply someplace far away.)
4. Teleport Scatter: (6th lvl spell) As teleport scramble but breaks up the incoming teleport and scatters EACH creature in the incoming teleport to a different random location. Variants allow only the caster of the teleport spell to arrive safely while all of his companions are scattered.
5. Inter-penetrate: (8th lvl spell): This ward simply causes all teleport effects entering the warded area to arrive in such a way that causes inter-penetration on arrival. All arrivees must succeed at a Fort save or die a grizzly death with their bodies embedded in the ground, floor, wall etc.. If the save is successful the arrivees aren't killed by the interpenetration, take 10d6 points of damage and are expelled into the nearest available open space.
After a couple of prismatic sprays through the scry sensor and a couple of scattered teleports, the PCs learned not stick their scry sensor where it doesn't belong and not to teleport anyplace that they can't verify is safe. I found this to be a workable solution because the PCs could still use teleport to get around if they wanted to, but they took their chances if they tried to launch a teleport attack on the evil overlord's fortress.
Tzarevitch
[/end vent/side track]
