Divination and transportation spells can pose problems for high level games, because of their ability to completely bypass the need for information-gathering and overcoming the obstacles of terrain. It is possible for the DM to overcome these problems with anti-divination or anti-transportation magic or by designing adventures where these won't automatically solve the core problem, but if this is done too often, it feels artificial. A better solution would be to change the spells themselves to be less problematic for the DM, yet retain their flavor and 'magic'.
At some point when we were still in the Alpha testing stage I suggested a solution for Find the Path that proved relatively popular and could be extended to other divinations and transportation spells and perhaps even to other types of magic.
The basic premise is that divination spells work as described in the rules, but in order to use them, the caster must have a focus. The focus must be an object from the place he is trying to scry/find/enquire about or belonging to the person he is trying to find/scry/enquire about.
Just how an object that can be a focus is defined is open to debate. To look back in time, perhaps the focus object must have been in the appropriate place at the appropriate time. To scry on a person, maybe it must be a body part or a possession of the person in question. Some feats might even be made to slightly relax the criteria of what qualifies for a focus object or even eliminate it altogether for specific spells or classes of spells (though the latter idea might defeat the purpose of having foci in the first place).
Applying this to Find the Path, the spell works as described in the rules, but in order to use it, the caster must have a focus - an object from the place he is trying to find.
It is entirely possible to expand this concept to other divination spells too. In order to scry on the evil priest locked away in his Tower of Doom, the caster might need a focus - one of his posessions or perhaps a lock of his hair.
Such an approach enables divinations to be meaningful and useful, yet it means they are less likely to break the game for the DM by completely obliterating his carefully-crafted "Find the Lost City" or "Who Murdered the Heir to the Throne" or similar adventures. The DM can, after all, control the availability of the items that serve as foci.
Exactly the same approach can be applied to some problematic transportation spells such as Teleport and its various variants. Maybe an object or a pinch of earth from the location to which the caster is teleporting is necessary as a focus. There could be some exceptions for 'attuned locations' - such 'attuning' could take a day-long ritual to complete and perhaps the number of such locations could be limited.
In principle, the idea of using foci could be extended even further and a similar approach could be used to limit, but not remove, other problematic spells, such as the various Save or Die (and Save or Suck) spells. Yes, the caster can transform a creature into a frog, or kill the creature instantly with a death effect, but not without having something (body part, prized possession,...) from that creature (the DM determines what counts). This could lead to interesting combat mechanics, as the caster could not just wipe out a powerful creature that the party has just now come accross with a single save or die spell. However, the party rogue (or even another character) may perhaps try to steal something from the creature during combat to pass it on to the caster, or the party Fighter (or Paladin, or...) might decide to disarm the creature (if it has a weapon) and throw the weapon to the caster so that the caster can cast his save or die spell. There could even be a mechanic tied to Slight of Hand, that when damage is done, the character doing the damage may snatch a meaningful 'piece' of the creature, such as a lock of hair from a humanoid or a single scale from a reptilian or dragon, or a feather from a griffin (you get the idea). Meanwhile, the caster can still be useful in combat casting other spells, such as buffs, debuffs, utility spells, direct damage spells, and so on that do not require a focus.
These further extensions (to Save or Die and other spells) may be taking the idea too far - the game is not Foci and Dragons after all, but using the foci to limit many divination spells and some transportation spells would solve many problems without eliminating those spells (and even adding further flavor to them).
For Teleportation, adding this requirement *only* if the character has never been there before might be reasonable.
I usually model my high level campaigns around requiring the PCs to divine information, so this is never an issue for me. As for non-magical information gathering, there will always be things you cannot find with magic.
Teleportation magic is a little more tricky, as I have always been a fan of requiring some kind of attunement, physical familiarity with the place, or teleporting "docks" that have the correct kind of energy that allows teleportation.