This started as a short tangent in my last post* (about using Gumshoe's "Core Clues" in Warhammer FRP), and grew long enough to need a post of it's own:
When I was running Savage Worlds on a more regular basis*, I borrowed from Gumshoe and set my difficulties for clue-gathering at a 2, usually with some added bonus/benefit if the PC got an 8+.
Didn't matter if it was an interrogation using Streetwise, or search involving Notice, the only way you could fail was by getting double 1's, and choosing not to spend a benny on a reroll. That way, the PCs either got the clue, or I was given an opportunity to narrate how some ridiculous blunder or bizarre coincidence kept them from getting the info they wanted.
It sounds better than it actually plays, unfortunately. I've found that some Savage Worlds players horde their bennies and only expend them in combat. Which means that in practice, there's still some danger of things stalling out because of a bad roll. It's still better than failing to get the clue because you rolled a "3" on a d8 and a d6, but not as much better as I'd imagined it to be. And should someone be so unlucky as to roll the critical failure, spend a benny and get a second critical failure, then you're adding insult to injury.
*: Link to the post using on "core clues" in Warhammer FRP
**: I'm still running my Savage Worlds fantasy game whenever my wife and I go visit our friends in Portland, but that only happens 4 or 5 times a year, so I hardly call that "regular".