I'm guessing that, at the times when the game informs you who the killer is but you don't get the option to imprison them for free, you know who they are, but can't prove it to the satisfaction of the rest of the nobility. So, while you know that imprisoning them is justice, to others it seems arbitrary and capricious.
Then they should just add two levels of the murderer being known: the one where you have no definite proof and the one where you have it. And let people be executed in the second case.
And let's face it: for those cases where the murderer is a kinslayer it has to be so that everyone knows for a fact that he/she is a murderer, otherwise there wouldn't be such a heavy penalty to diplomacy.