Sorry, but that's just a recipe for player vs. DM conflict. I think that during my spying background I was awesome at lying to people, whoever they were, so I should get +3 whenever I lie to someone now. I think that I also travelled a lot, so I know geography. Oh and I spied on several different countries, so I know lots about their customs, and I'm streetwise in their cities but also hung out with their nobles.
Then I would suggest that the DM needs to grow a pair. ;-)
The entire purpose of having a "background" and not just a collection of skills is that the theory would be the player would actually design a history of his character. What he did, where he was, who did he interact with. What was he good at. Thus... speaking personally as a DM... I would have worked with the player to actually have him create who exactly he spied for, why he was a spy, who were generally his targets etc. etc. You know... the PC's background.
That way... during play we'd be able to easily know that sure, in the capital city of the nation you were spying on... your Streetwise would easily apply, and your knowledge of the customs and locations of the people and places within it are under your purview. However... when you suddenly found yourself in the Underdark infiltrating a drow city... those same uses and knowledges from being a spy would not apply (or at least not apply unless the PC could give a really good reason why it should.) But it's up to the DM to accurately access the situation and the use.
After all... EVERYONE should be able to Intimidate SOMEBODY. There is always someone you have power over. That's the point of making it a STR or CHA check rather than a generic Intimidate check. And the +3 bonus to that STR or CHA check should occur when the PC is intimidating the absolute right person they have power over... which we know to be the case much more based upon their Background and who they've interacted with in the past, rather than just being generically good at browbeating everybody. A higher-level church official should be able to intimidate his underlings much easier than a random soldier could. And that should be made clear in the rules as to when that +3 might thus apply.