I personally have two fixes. a) have the paladin's code be his god's creed; anything that would make a cleric of said deity need atonement makes the paladin fall, and b) point them to classes without loosely defined 'fall' mechanics, but still keep the concept; i.e, Warpriest, or Cavalier. That way, they get all the roleplaying goodness of Paladin-style virtue without effecting what the rest of the party can or can't do (or at least no more than the guy playing a ranger or sorcerer can).