The problem that I'm having is that my players are constantly taking 20 with every step they take in dungeons.
This really gives me a headache:
If the party rogue has a sufficient search-modifier, the trap will be found with 100% certainty.
If the party rogue doesn't have a sufficient search-modifier, the trap will not be found and I gave them no chance at all. This will create bad blood for sure.
So what I'm looking for is a way (or two) to place traps in a dungeon in a way that they are immune to constant "take 20" and require a little bit more thinking/effort from the players part.
First, stop using useless traps. A trap that springs, does XdY damage, and that's it, is useless. All it does is cause the party to consume a cure wounds spell or potion. No traps in random locations that have no distinguishing features, such as a random tile or pillar.
Second, just to break your players' habits, introduce a trap that can (and will) be found but cannot be disabled with a simple die roll, and does not just deal a bunch of damage (so no getting away with your barbarian walking into it and soak the damage), so that in order to proceed they have to play smart. Self-resetting traps help avoiding the barbarian trick.
Examples:
(a) a trap that deals too much damage if walked into, but the effects of which can be limited by taking certain precautions [such as a trap made of gears which can be partially rigged to slow it down if you jam it with a stick or a rock]
(b) a trap that can be bypassed but this requires a series of skill checks [such as a pit trap that you can walk around if you balance on a ledge, improvise a bridge across or even climb on the ceiling]
(c) a trap that can be disabled, but only if you get to a location which is past the trap itself [so the Rogue has to find first a way like in case (b)]
NOTE that these, as-is, require smart play but still don't necessarily take advantage of the Rogue's skill ranks in Search and Disable Device: everybody may effectively find a solution for the trap if they play other characters. In case (c) only the Rogue still needs to do the job, but with other skills so this can lead the Rogue to wonder if the investment in Search/DD ranks was worth, so see next points...
Third, play with traps design and locations descriptions so that in order to reach the required DC to find/disable the trap a circumstance bonus must be gained, and this can be achieved by e.g. asking the DM the right questions to get hints on how the trap seems to work -> +X circumstance on disable device, or asking details on specific parts of the room where the trap is -> +Y circumstance on search, or trying to disable the device using a specific tool (as in previous example). The difference here is that you're trying to turn smart play into a mechanical bonus that only the Rogue can use. Still, everybody is technically able to provide the Rogue this bonus.
Fourth, consider a house rule where additional Disable Device rolls (no Take 20) grant hints, that the Rogue can then think about to improve his chances for smart play and get the circumstance bonuses as before, this way really making the investment in skill ranks valuable again.
Fifth, remember that traps work best when they ARE sprung after all. Try however to make a trap cause havoc (rather than damage), especially in the middle of an encounter: e.g. a trap that triggers just when the monsters arrive (and maybe is accidentally triggered by them after you succeeded at carefully not triggering it!), a trap that splits the party during such fight, a trap that causes hazards to appear during the fight, such as: holes in the ground, falling massive rocks, something that knocks creatures prone or slows them down, something that moves creatures against their will (flow of water, uneven ground, sliding stairs, pushing blocks, tilting tiles...), release dangerous substances (lava, acid...)
Sixth, if you use really challenging traps with a chance that they won't be beaten or withstood, use them to block optional areas and benefits such a treasure room or a shortcut, but not an area necessary for completing the adventure!