Some good ideas here! Thanks

[MENTION=22424]delericho[/MENTION] and [MENTION=6788652]G. Barrelhouse Esq.[/MENTION] while I think your ideas of "tortured until he broke" are solid, it doesn't quite work for what I'm looking for, since "death is the greatest mercy" seems a nihilistic and unredeemable stance. Also it doesn't give me a credible tie-in for "why deliver slaves to the aboleths/Underdark?" But I've got your ideas on my mental back burner, since the idea of the aboleths being ultimately behind his corruption is appealing, thematically showing the power of the Old Deep Ones' mental dominion...which nicely foreshadows elements in
Night Below.
Any sort of corruption could work. Possibly an evil sort of dryad seduced him. Or, if the bandit thing isn't absolutely needed, you could have him simply in league with a regular neutral dryad who's home is where the keep was built, sort of hell-bent on doing everything in his power to ensure nature "reclaims her beauty" in the region (of course he's really just lost sight of right and wrong). Something like that seems pretty cool. Bring in a lot of the old germanic fey stories for inspiration, where such creatures were more wicked and duplicitous rather than cute and pixie-like.
I really like taking him the "creepy, amoral fey" direction thematically. It actually reminds me of an old Marvel graphic novel called
The Raven Banner: A Tale of Asgard which had a villain who sold his honor to Nordic fey trolls and so he started to become trollish himself.
I was more focused on the Mercy tenet of the Oath of the Ancients, but there's another tenet that would be interesting to play off of and could feed into the "dark fey" vibe...
"Where Life flourishes, stand against the forces that would render it barren."
Maybe there's a sacred tree that is dying and that's what prompts him to start dealing with creatures of the Underdark seeking a cure at the roots? Maybe investigating the sickness of the tree/dryad is what leads him to confront an aboleth?
Maybe he was confronted by the classic adventurer dilemma: a pregnant mother monster, or a nest of unhatched/young monsters? And his decision to spare them put the paladin increasingly at odds with local villagers or other paladins?
Just brainstorming. I have a feeling once I hit something that sticks, I'll know it.
Well, perhaps he isn't enslaved by the aboleths...a moral dilemma that in hindsight was a lose-lose proposition. The classic drop the rock onto the people on the tracks (killing them) but preventing the train from slamming into the more people further down killing more. The only way out is to reject the boundaries of the dilemma and do something else. He didn't.
Going wit Mercy:
The Aboleths sent their enslaved into the world to abduct people. The Knight fought his way to the Aboleth lair and discovered that if he killed the Aboleth a contingency spell would dispel the magic of a wall of force "bubble" where the enslaved lived, and thus would kill all the enslaved. Showing mercy to the Aboleths ensured the enslaved would live.
The Aboleths let the enslaved free in return for their own freedom. However, returning to the keep, the knight discovered the place enslaved by the Aboleths, and these minions sent out to the world to wreak havoc. The people (and other heroes) rose up against them, killing them, and finally besieging the surviving knight in the keep and the freed (1st group) enslaved. In his hubris, he refused the "justice" of the besiegers not trusting a fair trial, and fought them, many of them no more than peasants with pitchforks. this is how he fell.
Oh man, I love this!
It does leave me with the dilemma of why he would then deliver people into slavery to the aboleths...if anything he would be fighting
against the aboleth slave masters...
Hmm, maybe there was something in particular that the villagers did that he found particularly abhorrent? Maybe they recognized (or just feared) that the people the paladin liberated from the aboleth were "changed". Even though it wasn't complete, they had begun to assume slight characteristics of skum (or some other mind/body warped servitors of the aboleth). Maybe there was an innocence to the Returned Ones / Changelings (due to mind-numbing aboleth magic) that he cherished and protected. When villagers started burning the Returned Ones / Changelings at the stake, he was outraged.
So maybe due to his code of honor he wants to avoid killing the villagers, and instead he condemns them to slavery to the aboleth. It's poetic justice. They get to experience what the Returned Ones / Changelings endured so they will have empathy for them (when they're hypothetically freed).
The "bandits" then include a large number of Returned Ones / Changelings who he is "sheltering." Though the truth could be they are manipulating him...or maybe some of them realize they're "changed" and wish to die...others wish to find a way back to what they once were (by killing their surviving families...or something equally twisted).
Tying this in with the "dark fey" theme, maybe the fallen paladin calls on ancient pacts with amoral fey who were tamed by his Paladin Order, knowing that he'll need extra strength if he intends to holds the ruined keep against organized militias or his former scattered brethren. Things like satyrs, bestial CN centaurs, "briar witch" dryads, possibly a shadow fey take on the death dog.
As years have passed, maybe his initial outrage has tempered and he is starting to have misgivings about sending folks to be enslaved...