The idea to add a quest to regain your oath is fantastic! Perhaps the quest could be different for each of the oaths.
On Withers breaking, it should be easy enough to just restrict Paladin as a class once the oath has been broken. This would prevent a player from using this feature to restore the oath, and allow them to select a completely different class from level 1 now that they are a fallen Paladin. Perhaps the oath restoration quest could still be there for the player to complete and restore the ability to respec as a Paladin (or available as a multiclass option).
"He that can smile at death, as we know him. Who can flourish in the midst of diseases that kill off whole peoples. Oh! If such a one was to come from God, and not the Devil, what a force for good might he not be in this old world of ours."
-Bram Stoker, Dracula
| 
