Stop making kill-then-search a workable response to the problems they face.
The first aspect of this is to make combat dangerous. If you don't want to make it deadly, then at least make it have long-term negative consequences, as Richard outlined.
The second is to throw problems at them that they can't solve just by killing things. In a dungeon, "tricks and traps" are a good option. Even something like a pit trap or a stuck door can make them have to sit down and think about how to deal with the obstacle. Just make sure that your traps aren't lame, and can't just be bypassed with a die-roll.
Another strategy that might work, depending on your player's possible interests, is to add a social dimension to your challenges. If the bad guy for your next adventure is the corrupt sheriff of a local town, or otherwise established in the social milieu with lots of allies and resources backing him up, it should be fairly obvious that they can't simply murder their way through the problem, or they'll just make their lives more complicated.
One strategy that combines both the "problem you can't solve through combat" and "making combat more dangerous" options is to throw something that's simply impossible to fight at them and will kill them if they try -- or, at least, that's impossible to take in a fair fight, when they haven't had time to prepare. This could be a single overwhelming monster, or something like a huge horde of orcs headed in the direction of something they'd rather not see rampaged through. The problem with this strategy is that if they're in the habit of fighting everything they see without thinking it through properly, even if it has been telegraphed fairly strongly that something is too dangerous to fight, things could end very badly for them and the game, so only do this if you're willing to let them get themselves killed. You should also probably set it up so it's clear that they don't have to fight whatever it is, and give them a lot of obvious escape routes, but set it up guarding (or threatening) something that they care about.