Your player’s characters sound rather well built. In general I tend to be okay when players do this, but if the party becomes internally imbalanced it can be a problem.
1. Without altering the CR of an encounter can we simply rearranging the layout to fix the problem? Some creatures really need to know their own strengths and play to them, especially when they have home field advantage.
Example: Kobolds are weak and the smarter ones know it. Rather than fighting in the open make the passages between rooms small and long. This forces the party to squeeze. As they go down simply have a kobold in the tunnel above or below stab his spear though the holes in the floor, or have a kobold or two at the end of the hallway firing crossbows down it.
2. If a caster is becoming a problem we start having environmental effects accounted for. These can range from disgusting to clever.
Example 1: Sentient soldiers can drop (the pathfinder equivalent to) a smoke grenade. Allot of casters need line of sight, and breathing in smoke requires a concentration check.
Example 2: We all know everyone poops and a fowl beast that has been locked up in a dungeon room will make it awful to be there. If you remember the reaction of reporters who tried to show what the post Katrina Louisiana Superdome bathrooms looked like… Needless to say anyone with a low fortitude or constitution may be sickened in such a room (throwing up, or just watery half shut eyes).
3. Replace a small combat encounter with an equivalent social one. Maybe the party needs something from here. Maybe as good adventurers they cannot mug an innocent individual or disturb a holy place. It may be that reputation is important, and you did say the players get hero points.
Example: The adventurers arrive in a room to find that the ornate vase they need for a puzzle has already been found by a Halfling Rogue. The Halfling, who thinks the vase will make a great wedding gift for his niece, refuses to give it up. After all he found it first, and the party must find a peaceful way to acquire it. If the party insists on a fight the Halfling willingly gives up the vase, but tells the locals he knows what jerks the party is. Later when the players are going shopping they find out that shop owners will not sell to them or only at inflated prices. Finding and apologizing to the Halfling may fix this, but more may also be required. This gets even better if a player commits murder and is considered fugitives by the kingdom (or equivalent principality).
4. If the problems come from fighter classes damage try challenging these same classes in a different way. Add new elements to traps and puzzles that cannot be fixed by killing.
Example 1: Integrate a heavy weight into a puzzle. In order to solve it the weight must be held up a curtain amount and lowered slowly as the other elements of the puzzle are handled. Maybe the players see a powerful monster in a room and must use the weight to bar the door closed.
Example 2: A particularly dangerous, potentially deadly, trap is easy to see but must be crossed before it can be deactivated. It may even be as easy as pulling an imbedded lever on the far side of the hall. To get over the trap climbing walls, digging a hook in the ceiling or similar feats may be necessary. It is best to include multiple checks in the scenario with two consecutive failures being defeat. Two successful climb checks (acrobatics can substitute) and a reflex save at the end as something gives under the characters weight can be very exciting.
5. This is a dangerous one if your players have a hard time separating their roll playing from the real world. Be very, very careful when using anything like this. Trying hitting the alignment button and holding down. Create a hard moral situation that has already gone wrong and the players are to blame. This tends to be easier with hardened players and games like World of Darkness and Call of Cthulhu where soul ripping horror is the expected theme.
Extreme Example See Warning:
While clearing out a goblin den the players come to a doorway at the end of one of the hallways. Both armed and unarmed goblins (equivalent to commoners) throw themselves on the players trying to protect the door. When the party opens it they find the dens nursery. The racial equivalent of teenagers charge the players with sticks and rocks trying to protect the younger children as they huddle in the comers in the room. One teen goblin runs at the players with a piece of paper and reads off exploding runes killing himself and several others. The players get their reflex saves, but can they survive the internal struggle of what to do next?
I hope some of this is helpful, and good luck with your game.