Actually they were not killing for killings sake, they were hired assassins. Its not really evil either. They are performing a service. A service thats legal just past the border.
Yep, I'm glad someone pointed that out.
Instead of Good/Evil factions, why not write the faction's with multiple outcomes or paths. For example, in the Fighter's guild you could pursue Ruthlessness or Valor (Or both, and just be a true mercenary), by accepting certain contracts or performing existing ones a certain way. Just a quick example, in the Tongue-Toad contract for the Fighter's guild, the "Valor" path, would be Allowing Tongue-toad to leave town, while Ruthlessness would be just killing him.
Mage's guild could be divided through Power or Knowledge. Power by any Means, or a simply a seeker of knowledge of the arcane Arts?
Thieve's guild would be Greed and Empathy. Steal from anyone and everyone, or steal from those who have too much as it is, and use it to uplift the poor. (Oblivion/Robin Hood style)
I was never a fan of "Good" and "Evil" Labels, I like motivation better. Ruthlessness can be a virtue for success, while Valor can be detrimental, but they define a character more effectively than Bad/Good.