After running this game every other week for a year, I'm wondering how your players are recovering their strain that quickly. Managing strain is the surefire way to nip this in the bud as the GM!
However, I don't feel like penalizing the players for playing the game as the rules allow is the right answer. My answer is to challenge them in combat in different ways, for example placing environmental conditions that induce strain, or events that lead up to the fight induce strain (a long hike, climbing the outside of a building, etc.)
Others have said it, but it bears repeating: your bad guys can pull the same tricks, and they should! And, now that the PC crew has developed a rep in a fight, your baddies might have some foresight to plan better.
Of course you need to be the PC's biggest fan and guide the story to be fun for all, but challenge births champions and it's the hard fights most players enjoy.