I had a player who wanted to play a Cleric, but was undecided on what domain he wanted because he didn't know what the tenets/ideals/rules to follow would be, and didn't want to have a personality or alignment forced on him. So I asked him what domain he wanted the most and we made up our own god: Zor, the Bolt of Justice was created! (Zeus/Thor, because we are sooo creative). We put down a couple key words (Justice, Merciless, Fickle) and Zor exemplifies those ideals to the extreme, even if they contradict sometimes. Now the Cleric can play as he wanted but still be able to disagree or have conflict with his own god and fellow followers in some ways. Plus, he doesn't have to agree with his god ALL the time, he's an individual character who can question whatever he wants.
So maybe make up the Patron with the Paladin. Get the general deal that happened to get his powers agreed to, but leave room for how and figure out why the Paladin feels cheated or sore at what the situation is now. My 2cp
While I dig what you teamed up with your player to come up with for your game, there's two factors here that are making your experience drastically different than mine.
The player doesn't seem to care about working together to build something with the DM, he is adopting a "my way" attitude. And he wants his character to openly defy and eventually utterly destroy his patron, not just sometimes disagree or occasionally have conflict with them.
He's decided upon an ideal for his vengeance oath: he wants to be a paladin of the Silver Flame and destroy all evil creatures. So his paladin oath is at war with his warlock patron.
I'd be okay with this setup if the patron was more or less in a "plotting the paladin's corruption, most of what I've told him is a lie, and the paladin's resistance is going according to plan" sort of mode, but after trying to discuss it, he insists vehemently that none of these things are going to be the case.
He expects the patron to not be plotting anything against his character, and be buddy-buddy with him even as he plots its downfall because if the patron were to be plotting anything, it would be a "flaw" and he's not building his character to have flaws. He just wants a cool-sounding anti-heroic backstory, with no negatives coming from it.
I'm pretty much done trying to discuss anything with him on the subject at this point. I've advised him that he can say his patron is whatever he wants it to be, tell me about what his warlock perceives their relationship to be and what the patron has told the warlock of its history. But he does not get to roleplay it or tell me how to roleplay it, assign it any stats, or build the patron in any way beyond what he's telling me is the backstory between patron and warlock.