I had an idea for a redeemed villain character when I was still playing 3.0. I didn't get to play him until I'd been playing pathfinder for awhile. Pathfinder mechanics mean that it wouldn't quite work the same way but my DM let me keep the backstory since he liked the concept.
Anyway, the original idea for the character was that he was a Rogue/Executioner/Anti-paladin. He had a horrible encounter with something that level drained him back to level 1 before he escaped. The experience was so horrible that he sought atonement, destroyed/donated most of his gear except for his now non-magical sword. Which he kept as a reminder of what he once was. He would then start leveling as a paladin. I think I had some way to re-qualify as executioner again but I don't really remember the details now. I also had the idea that his sword would slowly regain it's powers in an attempt to tempt him into using it and falling back into his old ways.
When fights broke out he would try to deal with things just using unarmed strikes, but he had the option to pull his old sword (the Rhoka), when things got bad. He had a high enough str that at low levels he was able to get away with it. But more and more fights he was having to pull the sword. It also meant that he approached even obviously evil enemies at least initially as being possibly redeemable. After all, he himself was pretty terrible and was able to be redeemed.
At one point We encountered a demon in the middle of a wrecked village. My character really wanted to attack the demon, but was forced to ask questions first. It turned out the demon wasn't responsible and never said anything that gave my character an excuse to attack him. In the end I had to let him teleport away since he wasn't "doing anything wrong" at the moment.
The game was supposed to be more roleplay centric then what our DM typically ran and was started in response to a player that had joined the group and essentially complained that things weren't "realistic" enough. He quit the group and so the DM went back to his normal sandbox game. Meaning I only got to play the character for a handful of sessions.
He was fun and was played very sub-optimally for roleplaying reasons.