This is not a combat focused group, this is a powergaming focused group. I had this problem with a few players, and yes <i>it's bad gaming</i>. Even in MMORPG is bad playing, because they cut off any other possibility and ruin the game for anyone (or anything) else. And yes, I think that it can be solved with relative ease.
First of all, it's a matter of system. Probably, you are playing 4ed, which heavily focuses not in combat but in powergaming, with superheroic characters nearly unkillable and with exponential power growth. It takes a EXCEPTIONALLY good DM to make a more narrative game, and it's nearly impossible with that group. And by that I don't mean a creative person or a good narrator: I mean DM that can handle conflictive groups, that can surmont impossible situations like that one, and that usually think outside the box. Anyone can be that... once he had spent 12 years mastering very different groups and systems. Most of us are only good DM, creative, ingenious or good narrators.
Once you had surpass the System problem (or assuming that you can't or you won't because you really like it, but I warn you, some systems are better suited for those excesses), don't abandon the combat. Make it lethal and unexpected. For what you say, they aren't used to think, only to exploit mechanics. Bring creative NPCs, unusual combat situations (don't think stupid rule things like "aerial combat" or "submarine combat" as creative, they are just weird and expected) like a group of really nasty goblins, that use enviromental advantages and guerrilla tactics (preventing, for example, long rests) good but non magical nor lootable equipment, poisons and curses in ways that the players don't expect: halved HP or stats, impossibility to attack directly, dire "real life" or long time consequences (limbs losed, permanent poisons and deseases), inability to heal fast (I think that if they are using clerics or sacred magic it's a possible way to take away their powers, mages could lose concentration because they can't sleep for days by a poison or curse); you can make a lot of combat-oriented booby traps (like hidden traps, stake barricades, incendiary floors, unreachable heights, great coverture, mounted archery, use darkness creatively -make the torches or spells the only light available, that make of them a perfect pointblank for spears or arrows). Don't make every fight a dying fight. Make an obvious necesity to maintain alive a foe (again, poisons and curses). Resign solos and elites and build armies leaded by powerful, character based NPCs, and make them retire if they are losing. Make every fight fast and furious, and very lethal. If they don't apply creative thougt aside from the random use of powers, make them bleed. Don't use every time the combat grid, and take a narrative approach to the combat. This, although being very combat focused, teach them how to think twice. In resume: Give them combat, but if they don't think outside powergame, make them lose.
Then, once you had make a point about the possible outcome of a battle, make more explorational or survivalist gaming. If they don't paid atention to the surroundings, use snakes, ants, bugs, food, wheater, rivers, heat and cold count. They can't rest until they have solutioned the survival issues, reducing combat effectivity. Use magic against them: again, non combat curses, alarms that create impossible barriers to their pass, pixies casting "confusion" spells and making them get lost in the wilderness. Give them not other option for his survival than think. Make combat-focused abilities useless in many situations. Don't give them shelter, nor rest, nor anything. They have to track their foes, not the otherwise. Make the lesser enemies run before them, using torched land tactics. Don't reward with experience random or dull combats. Don't give them loot nor magical items.
Give them time. Don't expend all your resources in one session. Some players would complain a lot. Some players would quit the game. Get rid of them if you see no other options, but more than one will face the challenge of survival. Then you can use hints, diplomacy and interpretation later. Don't put mechanics above interpretation (for example, a mage cannot use a spell if he does not actually says the magic words). Make them justify their combat decisions. Make their weapons rot and break. They can take it if you do this gradually and exponentialy.
I'm a Highschool Spanish teacher, and a DM, and I know that the players, like the students, must be educated prior to play well. That don't guarantee nothing, but is a necessary step to improve. They are people, after all.