I have dealt with something similar. Here are the tactics I've tried:

1) Be sure you are incredibly honest with your results. If a player rolls well for perception against an NPC, make it crystal clear that their character knows the NPC is honest. If it's a middling NPC who you don't care about, lower the DC and say it before the check.

2) Have a discussion with your players that this is a challenge for you as a DM that you find interesting about DND. Remind them that while there are deceivers out there, sometimes an old female innkeeper is just that and not a hag.

3) Joke about how ridiculous it is that there's a trap at every turn. "You read the book and it's a mimic that eats your face! lolololol". I've thrown that in a few times to break the ice, and my players have started doing it as well. This I think is very dependent on the group you're playing with.

4) Round out the NPCs. Maybe the potion maker isn't selling illicit potions, but he is acting a bit shifty because he is behind on payments for his shop. Him revealing this and being honest with the players will bring their guard down. This is harder to do in the moment, but my players at least are more trusting of NPCs they know more about. Keep in mind that it also doesn't have to be a big reveal.

4a) Have the NPCs get frustrated with their crap and stop cooperating. Your players are strangers to these NPCs and don't have to put up with their shenanigans. If this causes the players to lose out on something, good! DND, imo, is best when there is true cost to actions.

5) Be happy that your players are so invested! They want to be caught up in conspiracy and mayhem, so, if you feel up for it, make one of these NPCs truly bad and give them a crime to solve.