I played a paladin who fell and then redeemed himself. It wasn't the most dramatic of falls. He simply woke up one day to find he no longer had his abilities. It was lots of little things that just built up to him losing his paladin status. The DM had me make a list of all of the reasons that I felt caused me to lose my paladinhood; it turned out my list was a lot longer than his!
In the end, my character was praying for the soul of a recently-slain loved one in a ruined temple to his god (this was wartime, and the city had just been retaken from the enemy). He was approached by a priest who started a deep, soul-searching conversation with the character about love and duty and faith. In the end, the priest revealed that he was the ghost of the priest whose temple my character was praying in, and he was sent by their god as a final test. He then handed my character the holy avenger (only one if its kind; this was a super low-magic world) that he had quested for and failed to find.
His paladinhood restored, my character arose the next morning and led his army into battle against the big bad and his forces of evil. The clouds parted and a single ray of sunlight shone down upon my character. He died in single combat against the big bad, but did enough damage to him and his troops to cause them to retreat for good. The last scene of the game involved my character appearing in the feast hall of his god, where he was given a place of honor for all eternity.
