Hi Elf Witch,
Your DM sounds like she needs a break, but she could also assess what she can do to deal with the paranoia that her players must contend with. Here's some of my ideas and I may inadventently copy some others' posts as I hadn't a chance to read the pages through (sorry in advance!).
1. Make the penalties for not being heroes painful. The thieves guild example is kind of gold. Not only do the players don't get XP for handling the investigation themselves, but the thieves they hired were in league with the bad guys and the bad guys get tipped off. Well, I'm sure that your paranoid players told the thieves they hired to meet them at Such and Such Inn. That night, they get ambushed and attacked. After the encounter, they party should be able to put two and two together. Of course, having NPC's do your work for you means 0 XP and 0 gold--for everyone.
2. Make the efforts pan out to be nothing. The PC's hire the thieves guild, pay a huge sum, and get nothing. Or they get completely false information like, "We checked it out, only a couple of dogs guarding the place." (the rogues didn't bother to check it out, and don't care).
3. Bring the encounters to them. Whenever the players get paranoid and don't want to go to X, bring X to them. Make it unavoidable and better yet, unexpected. Make the paranoid PC's hunted. Adventure sometimes comes looking for you whether you want it to or not. In the example you provided, when the paranoid players are arguing that they don't want to stay at the murder scene and argue with the rest of the group about fleeing, that's when the city watch showed up.
4. When they argue or plan, that's when they are burning time for others to react. The DM should be thinking while the party is involved in a debate quagmire as to what the NPCs could be doing at this moment, particularly if you're in a dungeon complex with hostiles all around.
5. Trap them. When the paranoid players want to flee or go somewhere else, they find the way they came blocked--literally. A giant block covers the only entrance. Now they got to go find another way out by exploring.
Another observation is that some players tend to react better with assurances from the DM than from other players. In your Spellcraft example, as DM, I would have made the two paranoid players roll Knowledge (local) with low DCs to realize that a lot of people carry magic items, but something like a gem of true seeing is beyond the means of most people (and organizations). If the DM makes this presentation based off these player's roll for information, it's stronger than another player just making the case.
Some of these suggestions sound like railroading, but analysis paralysis needs to be addressed by having the situations come to the players and force their hand or flee.
It sounds like you're playing in Age of Worms AP from the descriptions of a few encounters. I'd be paranoid too if I was playing that. It was an awesome AP.