Give your players the intrigue they are so dilligently searching for
Take the hint:
If your players keep looking for something, it’s because they want to find it.
Your players are making Insight checks either because they want to, or they feel they need to (see "Abused Gamer Syndrome" below.) By your description, though, it sounds like they just consider this part of the game, and are pushing for some more social interaction.
Your players are investigating these NPC’s because they are interested in “what makes them tick.” Trying to squelch their curiosity about your world is the wrong way to go.
Provide NPC’s who have real motivations, and let your players figure out who are the social climbers, pious religious types, cowards...and yes, the occasional scheming villain.
Rolling d20’s is what we all came to do
If you described your NPC motivations a little more, maybe your players would stop calling for constant Insight checks, but maybe they just like that little ritual. If they are having fun rolling dice, why stymie that?
I figure the Insight checks are irritating you because you are getting caught a little flat-footed. (Maybe you tell them on a good check, that they don’t perceive any deceit, and they are never satisfied with that?) You know the Insight check is coming, so just have some tidbit ready for them.
If the NPC’s motivations and emotional state are less of a mystery, the party will know better where they stand. A few examples:
- Frantically worried about the person they’ve asked you to rescue, and is barely able to stay calm
- Sizing the party up, considering whether to invite them into a guild or secret society (a la The Harpers, etc.)
- Fairly disinterested in the quest, per se and primarily interested in not offering too much reward
A more intriguing adventure
Consider running an adventure where a few different NPC’s are trying to get the players to do slightly different things. One says, “Drive the goblins away.” Another says the undead are the real threat, and the party should try to strike a deal with the goblins.
Maybe one or two NPC quest-offerers are outright villains. Not all the others need to be saints, either.
So, is this Abused Gamer Syndrome?
You mentioned you thought your players were suspicious of quest givers because of fiction they may have come in contact with (and I've answered accordingly). But comments and other answers bring up the possibility of this being Abused Player Syndrome, that is, a defensive style of play caused by playing too long with a DM that was constantly trying to trick the players.
You can ask your players if they've played with a DM like this, and what they think about it. If the Insight checks are just a rigamrole players feel they need to go through to keep from getting shafted, let them know out-of-game that's not going to happen in your campaign. But still, back that up with the additional details about the NPC's.
Adding an in-game social aspect to your game
Your players are looking to spend more time figuring out social puzzles, rather than having a few sentences with Mr. Quest Exposition to get directions to the next dungeon. Find out how much more time the players want to spend doing social interaction, and adjust adventures to accommodate, if you possibly can.
Don’t try to get your players to stop taking initiative and looking for adventure. That will put your players into reactive mode, a very dull way to play.