+1
As I said in another thread, I think there could be laws changing overtime, so that the king wouldn't have justice in every domain right at the beginning, but it is just ridiculous that one cannot do anything to retaliate against a known traitor. As someone else said, the AI should also understand the concept, so that it would be far more riskier to plot against a liege.
About banishment, I wonder if the guy still keep his claim. If yes, I think it should still be relatively costly, since it is somathing extremely powerful to do. If there were any mechanic to redistribute immediatly the land between known claimants, I could accept less tyranny, but right now I think execution should be more... encouraged, but not banishment, since you can sometime break a very powerful vassal by doing this and doing so without any penalty would be strange.
Also, good narrative with the Norwegian sense of justice, Me_.