The question I would ask you is: Is the problem coming from inevitable gun fights (planned by you or easily foresaw) or the result of the PCs actions?
If gun fights are planned or unavoidable for any reason, for you and your players, a good challenge is what you guys need. Not bigger badder guys with even bigger fraggin' guns but challenge. Force your players into unusual situations, something they can deal with but are not necessarily equipped or used to. Think a little outside the box. Toxins specifically aimed at Trolls (if the story can explain it), chambers filled with suffocating and/or explosive gas, places really really cold or filled with electrical sparks, situations that will make them think twice about staying and shooting people. Or make consequences of shooting more dire. If they're invincible, their lovers, friends and family might not be. Or I can give you an idea by giving an example of what things my GM throw at my character Smiley. To make it short, Smiley is an assassin using cunning to reach his target up close and kill them with his bare hands (as an Mystic Adept, he's really good at it). He is really tough, magically resistant and really good at avoiding getting hit, so my GM really rarely bothers with tough fights and works on making it tough to reach it instead. My char had a target to kill, a paranoid scientist and engineer, a real genius, working as a freelancer for who pays most. He's a loner and doesn't even know how to fight but... The target had recently and secretly implanted himself with a device that would make everything he owns and himself explode upon his death. It took some planning and a lot more improvisation but I did it. I don't really need to mention how a bad idea it was to just snap his neck and collect the paycheck. Circumstantial difficulties or penalties will make your fights more challenging without trying to pit them against their equal.