Personally, I like the idea that was passed around before. "Clerics with the travel domain would get a teleportation item at level 16." It's a high enough level that it'd not be easily attained... and it makes the cleric have to pay something to get it (one of their domains). Makes sense to me...
Also I find that if you work it out with the GMs, you can "speak with the dead" on quests. You can check your crystal ball for signs of what the future holds, you can scry, or try to block scrying. Most of these things would be no good unless you have a GM there anyway, and most GMs will give you a reasonable check in order to succeed.
Player: "I'd like to try scrying to find the man named X."
GM: Decides that the DCs will be 10-The Continent He's on, 20-The City/Major Geographical Place he's in, 30-Within a mile of X, 40-Shows you exactly where he is. "Alright spell craft check."
Player: Rolls 5 + Modifier 10 = 15
GM: "X is somewhere on Mistone, you can't desipher where though."
And there you go, instant scrying. (Ok so it's not instant, but it sounded good)