My current campaign is reaching the level where I have to worry about Divinations and Communes and Legend Lore, and I have to tell you it's got me flustered. I'm not as good at spouting nonsense as Piratecat

.
The campaign is very tactical and combat oriented now, but the party is about (they hope) to break into the Underdark, where much more intrigue awaits. Theoretically.
But how do I keep secrets from Divinations and Communes?
"Is the leader of the bugbear camp secretly allied with the Drow?"
"Does this newcomer we're talking to plan to betray us or kill us?"
"Is the item we're looking for in the City? [Yes]
Is it in the North or East end? [No]
Is it in the South end? [Yes]
Is it in . . . . . "
And by the time the Twenty Questions have been answered, they know exactly where to look for what they're looking for.
And that's just the start of my concerns.
My BIG worry doesn't concern the PCs so much as the NPCs, who are often going to be led by someone who has access to higher level divinations than the party.
A couple Legend Lore/Divinations to learn about the party and their allies, or movements, and then one or two Commune spells later, they've been pinpointed. And then, they die.
Resolving Divinations cast by NPCs is going to be tough, because I have to decide whether this 18 or 20 Int friend of the cleric casting the Divinations is going to be able to figure out whatever cryptic clue he'd be entitled to. To be fair, he probably would.
So there you go. How do I preserve intrigue in an environment with high-level divinations, and how do I preserve the party's life against enemies with high-level divinations (who are also more powerful than the party)? Bleah!
My initial thoughts:
1) Make Divinations very vague, and allow one/week.
2) Up the XP cost for Commune, and allow one/week. And make it so that many gods/gods agents don't know the answer to internal questions (who is friends with who, what someone is planning, etc.) I can't believe they'd want to be constantly pestered, anyway.
3) In such an environment (where divinations are *everywhere*), magicks will have been developed to protect one from such divinations, especially while at home. I'll probably make Non-Detection amulets cheap to make/acquire (well, relatively cheap).
(Big One)
4) Create a new magic item/system . . . centered around the idea that it is difficult to create
portable powerful magics, easier to create powerful magics that stay in one place.
Possibly because they need a heavy, stable "energy source" to power them. This would allow merchants, nobles, etc. that had such energy sources/built their homes and shops near such energy sources to have access to protective magics that they would not normally be able to afford.
Still playing around with this one.
All I know is that I don't want a world in which every medium-level Good Guy and Bad Guy is scrying and divining so much that there's nothing left to do except teleport and fight, teleport and fight.
I am eagerly waiting to hear ideas from those of you who have already had to deal with these issues.