Celebrim
Legend
Honestly? Give them more redeemable enemies, enemies that they could reasonably save...
So far, I don't think this approach has really occurred to the party.
The thing is, the cult leader wasn't a completely unredeemable character. She believed that the world was ruthless and unforgiving and brutal, and because of that anything she did was justified to change the nature of the world. She actually has a sympathetic motivation (which I'll currently keep quite about), but suffice to say that it could be summed up as she wants a world with less pain and grief.
As far as the cult leader is concerned, she's a hero. She thinks she is one of the good guys, and the behavior of the party is exactly the sort of ruthless brutality she would have expected of those that call themselves 'good'.
In fact, to give a bit of a campaign level secret away, the literary idea animating the entire evil organization is "there is no evil a man will not do when he believes that he has been wronged". It was my intention to make most of my villains for this campaign be at least two-dimensional complex individuals who were people that the players could come to like, respect or even empathize with to a certain degree. Many of my villains are or are going to be quite charismatic. They are intended to 'tragic heroes'. In fact, I strongly suspect that with some groups at EnWorld, they'd end up joining sides with them because a lot of their motivations and self-identity parallel popular sorts of thinking today.
A lot of the reason that players are bloodthirsty is that they have learned, from gaming experience...
This group of players is largely inexperienced. About half of them are playing for the first time. So, while there is some truth to what you say, I don't think that is the primary reason PC's tend to be ruthless and bloodthirsty. I think the two primary reasons why PC's tend to behave like bandits and murderers is firstly that they are playing a game and so (somewhat reasonably) have foremost in their minds a competitive mentality. And secondly, I think that PC's tend to behave in a quite bloodthirsty manner because humans tend to be quite bloodthirsty and goodness is so rare that people have a hard time relating to it or even imagining it. We are, in Tolkien terms, largely 'orcs' and are heart is given to the wrong gods. That is the reason that evil is so easy and good is so hard. That is the reason that when we imagine and fantasize about our superpowers whether in movies, books, games, or any portion of our fantasy life, they tend to revolve around beating people up good and making/commanding other people do what we want them to do.