Deafen them.
Cut out their tongue.
Cut off their hands and feet.
For really bad criminals - all of the above.
Decapitation.
Castration so they won't get any heirs.
Forced removal of children so they can't inherit the criminals goods and title.
Brand them with a hot iron.
The only one of these I think have merit is the branding one (though I guess cutting out one's tongue isn't too over the top either I guess), but even that I think would only be alright if it was reserved for a character that was a habitual repeat offender - akin to a three strikes rule - thus giving the deviant player the choice to relocate towns/regions before risking such a fate if caught one too many times in their current locale.
But then though there is the issue that if such a punishment mechanic was to make it into the game who's to say that a governing body won't simply be heavy handed with it and brand everybody for the slightest infraction, without any prior warnings (though I guess that in itself is a motivator to drive a storyline of rebellion over such abuse, I don't know maybe it'll work out - maybe revolts will have a place in the game regarding Casus Belli and the Dance of Dynasties, who knows).
Castrating someone or taking away someone's heirs though is way over the line. I understand high risk, high reward (half the fun in undertaking deviant behaviour, both in RL and IG, is the gambling high of the risk), but messing around with someone's ability to reincarnate into their family line is beyond punishing the character, it's just blatantly punishing the player. I find this more heinous than the physical crippling options given for the "really bad criminal" above it.
Lets not forget that not all deviant players are going to be trolls, some are just roleplaying (whether as a full-on rper or casually as a rpg gamer) a deviant character. I understand the want to punish/restrain those who engage in deviant behaviour just to be arseholes, but let us not go around throwing the baby out with the bathwater in doing so.
I don't know I think for most crimes reparations (financial or service, to the wronged party or to the community), public shaming and restrainment (e.g. flogging, pillory, stocks, etc), perhaps some jail time (if they work out a system to make it engaging) and/or banishment, together with the hit in spirit loss and reputation with the passing of the sentence, should be fine in providing adequate risk for a deviant's reward.
A thought about branding (which I'm not totally opposed to, within reason), you could replicate the same thing to a degree with using a "scarlet letter" like device on a criminal, perhaps a neck manacle with a sign or symbol hanging off it advertising the players crime and generating negative impacts with that player's interactions with NPCs and OPCs.