I feel like if your character is prevented in protecting and then again in avenging his king, you run the risk of him looking incompetent, stupid, or pushing a series of events that could come off as awkward. It feels more natural to me if there are unknown circumstances to the king's death which cause him to not pursue vengeance or leave him with no clue of who was responsible.  As someone else mentioned in this thread, maybe he saw a reason for the king's death to be necessary, maybe the king killed himself and everyone just assumed an assassin got to him. Perhaps the king's death was someone else's fault and he was trying to protect them.

What if instead of being pushed into exile for failing to avenge his king, what if it is a self imposed exile. He is expected to get revenge, so he sets out on his journey, but knowing that vengeance can't be attained he vows to never return.