I think that when it comes to dice rolls and natural 1s, the key to remember is that players should only roll the dice when there's a possibility of failure, and when that failure would actually be interesting/meaningful. So tying your shoes should never call for a roll in the first place. If a paladin gives a truly sound, even exceptional argument to persuade someone, then the DM should think hard about if the paladin needs to roll at all. And if the paladin does need to roll and rolls a 1, then that can represent the NPC simply being stubborn or illogical or erratic, something that doesn't require the paladin to retroactively not have made a good roll.
