#Rebels are often someone important

And you don't want your ruling class to see their friends getting beheaded, that's saving up trouble for the future. Also people of this class have something to lose in terms of social standing when in exile and would need to be supported by a foreign power or overseas allies to maintain that. It allows you to see your distant enemies more clearly.

It's important here to distinguish between a rebel and a recalcitrant peasant. Peasants aren't important and can happily be executed or otherwise posted off to labour camps and worked to death.

#Exile allows for rehabilitation

Or even just a local change of policy. You don't want execute people who could be useful in the future, you never know when you might need [a new king][1] for example. Last year's rebels could be next year's government and you don't want to be the administrator who put all their friends to the sword. Exile them, keep tabs on them, and you can recall them when the game changes and send the next round into exile.


  [1]: https://en.wikipedia.org/wiki/Charles_II_of_England