Before prisons were a cost-effective way to deal with offenders, exile was actually more common than the death penalty. It was especially if there was some place you could offload your criminals, like America or Australia. Despite being apparently harsher, british legal code in the 18th century caused less death penalty than the preceding one, but many deportations.
Exile would be very fitting, especially since D&D worlds have many gradual exile a real possibilty. You're a regular murderer? Go to some place the king wants to colonize. You are really the worst kind of offender with tremendous power? Get planeshifted with varied degrees of hardship (it's arguably better to be planeshifted to the forgotten realm than to Krynn than to Dark Sun than an elemental plane...) youu're really the worse one, a BBEG of tremendous ability to come back? Get Imprisoned. No death penalty, everyone is happy, and we get a good explanation for villains popping up everywhere along the sword coast, it's just a society with a death penalty taboo meteing out justic ;-)
TBH, there is so much discrepancy in individual power that I think a level 20 spellcaster would instead have his death sentence communted into community service. "You, you can be hanged or quartered. Or you could go to some-place-we're-at-war with and just be you."