Justifying any means by the ends really is a fringe philosophy and you should expect the townsfolk to treat you accordingly. The Crusaders already (for the most part) do that, and you should know from experience that they are widely disliked and often in trouble with the law because of it. You really should expect no less.Right now this new "not allowing in the cities" really makes me confused as to what I should do with the character. Because frankly, Delmon's not an assassin or murderer. He doesn't do illegal stuff. He just uses means to an end...
To give you an admittedly poor modern day metaphor, think of it as you garroting notorious members of the mob or performing drive-bys on violent gangs. Sure, your first time around people might look the other way, but eventually you're just going to become part of the problem in their mind. Its the same thing with backstabbing. You may choose to only backstab those generally associated with having dubious characters, but soon enough you'll just be another assassin/thief in the public eye.