The all-or-nothing nature of 'loosing' Paladinhood is also a particularly blunt instrument- either you're in the favor of your God, or you're not. There is no mechanic that reflects 'skating on thin ice' or a gradual descent into naughtyness- you're either one of the Divine Elect or you're a nobody. So here's an alternative:
Taint Points: Paladins start with a Taint score of zero. For every unlawful act they personally commit ('unlawful' in this case meaning out of alignment with the goals and values of the deity they serve), they gain one Taint point.
Taint Points in Play: Whenever a Paladin invokes a class ability, spell, or spell-like ability, roll 1d20. If the result is less than the current Taint score of the Paladin, the attempt to use the ability fails and that ability can not be used again that day until the Paladin has slept and prayed (i.e., the next time he has the opportunity to prepare spells for the day). This applies to casting spells, lay on hands, auras, turning undead, immunities, and other supernatural and spell-like effects, but not to base attack bonus/THAC0, level/attribute determined saving throws, weapon and armor use, etc.
Getting Rid of Taint Points: To get rid of Taint points, the Paladin must complete some action to bring himself back into the favor of his deity. This can include:
- An Atonement spell cast by a cleric at least two levels higher than the Paladin. The cleric will likely require the Paladin to complete some task (possible a Quest/Geas) to earn the spell, but not one as complex as the quest option described below. The cleric may also require a donation to his or her temple.
- Tithing 5% of the Paladin's current wealth to an appropriate temple. The donation can be cash or equivalent magic items/treasure. The donation must be for the use of the temple- the player/character can not, for example, donate treasure to a temple that is part of their own fortress or castle or donate to a temple that they are in control of. If you ordinarily give XP for class-appropriate treasure spending, the character receives no XP for this donation.
- Undertaking a major quest for the appropriate deity or temple, for which the character receives no XP and donates all recovered treasure to the temple, might be worth wiping a Taint score back to zero.
- Laboring under a vow for an appropriate amount of time. A god of war might want you to refuse using missile weapons for five combats. A god that protects the poor might want you to give generously to anyone who asks for money or other help for a month. Any god might accept fighting without magical weapons or armor for an appropriate number of combats or using crude and simple weapons (possibly ones that you are not proficient in) like daggers and clubs.