I'm a Banana, the point isn't that a Paladin can be evil without being a Death Knight, it's that a character who claims to be good and THINKS they are absolutely good and righteous in their cause has a license to do very dubious things to get to their sworn enemy.
At that point, though, it's just an Alignment Debate.
Player: "If I do all these horrible things but for a Good Reason, I'm still Good!"
DM: "Uh....nope."
Not that alignment matters much in 5e, but it's still a thing the player and the DM agree on a PC being. And if he's Evil you've got no house rule against evil PC's, it shouldn't be a big deal - he's not going to fall from paladinhood. The only way to do that in 5e is to break your oath, and it's a deliberate decision, not something that happens accidentally. In other words, the alignment mostly just describes what the character is like, it doesn't restrict them to certain classes or anything.
If you DO have a house rule against evil PC's and your group determines he is one, it'd be a good idea for the player to retire the paladin and whip up something that EVERYONE agrees is not evil.
Regardless if you think Paladins should be allowed to be evil without being something like Death Knights (and I do disagree with you on the Oath of Devotion being evil like that. That clearly goes against tenets such as helping the most and harming the least), by the Oath of Vengeance, they can do a lot of things that would normally not be good or even neutral because it fights their "sworn enemy". And outside of coming up with a variety of NPC scenarios to combat this and suddenly make the focus all around this character, there's very little to deter the character from those actions outside of the DM just saying "hey don't do that", which I try to avoid when someone is role playing a character very well and they technically aren't doing anything wrong. If he's a zealot who believes alcohol is the source of all evil and he's not going to stop at anything until every last drop of it is destroyed, then that's great. I just wish that as a Paladin, there was more in the rules to describe conduct
The problem you are describing - "outside of coming up with a variety of NPC scenarios to combat this and suddenly make the focus all around this character, there's very little to deter the character from those actions" - that's a
player issue, not a game rule or game fiction issue. That's an issue with a player playing a character that no one else wants around, and that ruins the fun for everyone else. It's like playing a kleptomaniac kender or a mage who can't help but
fireball the town or the evil character that's making an armor out of the skin of children and so spends their downtime kidnapping and murdering local newborns because "that's what my character would do." Or even something less severe, like the craaaazy gnome wild mage in the grim dark Ravenloft Meets Dark Sun campaign. (I say this as someone who is playing a crazy gnome wild mage.

)
In D&D, if you make a character that wrecks the experience for other players, I don't hesitate much to say that you're playing D&D wrong.
An inappropriate character isn't a problem with their role-playing ("This is totally in character for my sociopath!") or even necessarily their character concept itself ("The rules don't say I CAN'T be a klepto!"), but it's a problem because it ignores that everyone else needs to have fun at the game, too, and the character is failing to make the game more fun for everyone. It's not the end of the world to have to swap out a character, and it shouldn't even be a big deal, but it's not something you can solve through in-character rewards and punishments, really. If your core character concept is disruptive, your character needs to ride off into the sunset.
You as a DM may want to put tighter rails on what your party is or is not, but I like to reward great role playing and that usually starts by allowing a character to be the character they imagine within the context of the written rules (hence this debate) and a little tug and pull.
It is entirely possible to fantastically role play a horrible, disruptive character who should not be played. In a Dark Sun game, I had a mul former slave who wanted to overthrow the sorcerer-kings, but he didn't mesh with the more amoral and self-interested party, so I had him ride off into the sunset and made a character who COULD adventure without their personal crusade. It's not about the quality of the player's performance, it's about the quality of the player's consideration for the other players.
Like, I could play an Oath of Vengeance Paladin who believed that Alcohol was the greatest of all evils in a way that wasn't disruptive. It'd be mostly downtime color, maybe I give everyone in the bar grumpy looks, maybe I try to get in good with the local lords and kings and convince them that temperance is the first of all virtues, etc. There's nothing inherent to the character concept that means "I am going to make this game about me, now." If a player interprets it that way, it's not a problem with the paladin - it's a more problem with the player.
Which is why talking to the player about this is probably a better solution than ANYTHING you could do to his character.