>Just imagine Lord of the Rings with teleport
Actually, if your problem is in creating an atmosphere like LOTR, it isn't with teleport. Magic in LOTR isn't even consistant in and of itself.
The best example of this is to read the LOTR RPG sometime and see the magic system they use in order to simulate magic from the book. It is advised in that book, that although lightning bolt type magic is available and freely choosable as a spell, you should prevent players from casting it very often. It points out that although Gandalf seemed to have the ability to throw a lightning bolt at enemies (and, although I haven't actually read the books themselves, hinted that Gandalf cast a lightning bolt at someone during them) he didn't use them against every enemy he encountered, even really hard ones because that's just the way LOTRs works. It suggests that spells with actual effects that weren't subtle either not be allowed to players or if they used them too often to stop them.
The real problem with trying to simulate LOTR is that it is actually a low magic, low level campaign and world. I know that the LOTR: is it high or low level debate has happened many times, but I can tell you that the game and world you are looking for is one where the average PC is around 2nd or 3rd level and doesn't really gain levels. It gives you that feel without needing to change much at all. All you have to do is assume that even the most powerful people in the world are level 7.
I don't really see teleport as the problem. When you have that high level spells, there are MANY things you can do that destroys the atmosphere you are looking for. I know the one: Scary, mysterious, dangerous, "you could die at any moment", you have to be smart to survive.
All of these can be accomplished. Just make the PCs low level. Go into the Underdark when you are 3rd level? A fireball might kill the party. You could be caught be a random patrol at any time and they COULD kill you. You can't just teleport out or use powerful magic items, as you don't have them.
D&D has its own feeling at each level. At low levels it is dangerous, getting there is half the problem. At mid levels, you can avoid some of the perils of travelling, but you are still faced with choices: use fly to get over the forest or have a fireball to defeat the BBEG when you get to the other side. At high levels, you start getting into more of a "We will do the impossible and take on the Ancient Temple of <insert ancient god's name here>, just the 4 of us. We can teleport out in order to avoid patrols at night and teleport back in afterwards as there is no way we can win in one day."
None of the feelings is WRONG, it's just the way D&D IS. At level 10+ you are getting very close to being more like superheros than gritty heros. Expect players to find away around any type of barrier. The only thing that should worry them are equally powered villians and traps and barriers designed to be at their level of power. Want to play a high level LOTR game? Sauron has to have the power to stop teleportation into mount doom or the players have to be too low powered to have that ability.
Majoru Oakheart