Now having followed the story most players would, I think, have opted to off him.

If you offer a choice here and don't offer the same choice at non-important events, the fact that you offered a choice would make it look suspicious and the player would think twice about whether or not to kill the character. In other words the player's choice will partially be based on the fact that the designer offered a choice in the first place, thus the choice option would break the immersion and the player won't be emotionally attached to the choice. If you want to elicit emotional response from the player, allow him to make the choice based on how he interacts with the game world, rather than simply making him choose A or B in a dialogue. Let's take the example with Ezio. You hunt the traitor down and once you have, you're offered to choose whether to spare his life or kill him. If you decide to not kill the traitor, why would you be hunting him down in the first place? It's not something you would be doing, if you had doubts about this traitor being a traitor. So, as a designer, what you should really do is make it so that successfully pursuing the traitor or not was the actual choice you as a player make. If the player has doubts - he might abandon pursuit, if he doesn't he can kill the NPC. However, this gameplay addition implies that failing a mission might be Ok, and thus leads us to a mission-less system of an open world - I'm not sure if it's possible to implement this kind of gameplay.

The other possible option would be making it so that completing a certain optional side mission would reveal the truth about the traitor and change the player's pursuit and eliminate mission into something else, like pursuit and interrogate.

Interactive fiction or as I remember it from my youth "Choose your own Adventure" books often has a crossroad decision virtually at the start. One decision leads you deeper into an adventure and the other is an immediate end to that story. In a few of these books, that immediate ending usually read something like this: Your next six weeks were spent quietly and then you died to the alien invasion. In seeking to have a game that is interactive you open yourself up to the reality that the path you take is still at the mercy of the writers.

You cannot truly have a successful interactive adventure if the final outcome is immediately one event or another eg. Stopped the aliens or died to aliens. It needs to be a multiplicity of endings some of which are defeats, some are wins and importantly, some are compromises. Moreover the premise will never truly succeed if you imbue absolute opposites i.e. good and evil. Absolutes don't work well for the most part as it very difficult to produce reasonable "compromise" endings which is what I think you are looking for in a game. Either way you still exist at the mercy of the writers.