You don't necessarily have to roll anything
I'd recommend reviewing the basic game flow, which is where I think the root of this problem lies. But to understand what is behind this answer: if they don't believe a fellow PC, that's their problem as players and characters. That's not your problem as the DM. They need to work out their trust issues as characters in the story. From your comment...
The players as people are all friends in real life. Session Zero
established that the characters do not know each other before the
adventure. So they are not allies. How much at first sight they trust
each other should in my opinion depend on how charismatic the player
is and in the long run on the Characters actions.
Letting that happen as the PCs play/adventure together seems a more organic way for the truth to come out. You are trying to force that, so it's no wonder that it seems awkward. It is.
The party has no reason to believe him. They ask for an Insight check.
Beyond a conceptual objection that "do I believe him?" is not a fair question to ask (because that may vary with table play styles) I'll raise a point of order: the DM is the one who does, or does not, call for ability checks.
- The DM describes the environment.
- The players describe what they want to do ... the DM listens to every player and decides how to resolve those actions ... the DM decides what happens, often relying on the roll of a die to determine the results of an action.
- The DM narrates the results of the adventurers’ actions. (Basic Rules, p. 3)
The DM is not required to call for a die roll. The party does not call for ability checks: the DM does. Only call for a roll of the dice when the outcome of a result is in doubt.
Ability Checks
The DM calls for an ability check when a character or monster attempts an action (other than an attack) that has a chance of failure. When the outcome is uncertain the dice determine the results (Basic Rules, p. 61; emphasis mine)
Your criteria include:
- Player X should have a reward for his high charisma score.
He already does: a bonus (+3, +4, etc) to Charisma based ability checks.
You, the DM, know that the player is telling the truth - the outcome is not uncertain. The problem is a matter of communication between the player characters. If they don't believe him they don't have to. Let this play out as this team slowly incorporates this new PC into their adventuring group. A more organic way to build that trust is through the "slow reveal".
What is the real problem? Communication and trust
PC X has information but the other PCs don't find PC X to be credible. What kind of party dynamics is this? Dysfunctional. They need to resolve this by adventuring together and by learning to trust the new character more. A die roll is no substitute for earning one another's trust.
Proposed solution: the slow reveal
The PC may be frustrated initially, but if they have the truth on their side your task as DM becomes to dribble out bits of confirming information from other events, or other sources, which support, or confirm, what the PC told the other PCs when he shared his back story information. Let them role play their way through this trust issue - let the other PC's learn the truth of PC X's input, based on corroborating information that they learn organically (within the game world).
Examples:
The town leader's ex-wife meets them in a tavern and imparts some
confirming info.
The town leader's former business partner provides another piece of
the puzzle.
Evidence (material, a missing item is found) arises that confirms
what PC X was saying).
If they learn it organically it's better narrative support than a die roll.
This part of the answer challenges the frame of the question where the solution to the problem presumed to lie in a roll of the dice. That approach deprives the DM of some of the flexibility that this particular edition of D&D allows for in making rulings.
But I want to use the dice.
- The outcome should not be predictable. There should be a chance to
fail, just as when someone is lying
OK, here we go.
Contests: should I use them?
Both participants in a contest make ability checks appropriate to
their efforts. They apply all appropriate bonuses and penalties, but
instead of comparing the total to a DC, they compare the totals of
contest. That character or monster either succeeds at the action or
prevents the other one from succeeding. If the contest results in a
tie, the situation remains the same as it was before the contest.
You can have the players engage in a contest between each other - your opposed rolls idea is supported by the rules, but it's messy mechanically, as you have discovered.
If you choose to have a contest, then Charisma(Persuasion) versus Wisdom(Insight) fits the "appropriate to their efforts" requirement. But the party believes that he is trying to deceive them, right?
So roll it as Insight versus Deception.
They already don't believe him. From the PoV of the party (not including PC X) it makes sense. Cassandra ran into a similar problem in the Trojan War. She told the truth and nobody believed her.
If they win the contest: do they believe him? You, the DM, have to decide that.
If they tie the contest, status quo, they still don't believe him. And he's telling the truth.
If they lose the contest .. do they really believe him?
You can force the issue as the DM by ruling that
"OK, he won the contest, he's telling the truth."
Or to the player of PC X you say ...
You won the contest, they think you are telling the truth.
Which points to this question: why is there a die roll?
If that's what you'd rather do then have a Contest. There are a few weakness in that approach so here are some alternatives.
Alternate 1: don't oppose the Insight check
Have the PC in the party who has challenged PC X roll an Insight check with advantage. (Working Together, p. 62) If it succeeds, they are confident that PC X is telling the truth.
Alternate 1a: Unopposed Persuasion check
Same as above, PC X rolls a Persuasion check but if the roll fails and you want to reward them for Persuasion (per your comment) ...
I want to reward the player that tries to convince the others for a
high persuasion score.
... then he rolled the dice, and failed, and you reward him for ... what?
As you can see ...
The dice aren't that helpful in any of this PvP: that's a design problem
Here's a deeper look at the mechanical problems. The group is "working together" (Basic Rules, p. 62) and the group (or whomever challenges this PC's story) get a roll with advantage
Sometimes two or more characters team up to attempt a task. The
character who’s leading the effort—or the one with the highest ability
modifier—can make an ability check with advantage, reflecting the
help provided by the other characters. ... A character can only
provide help if the task is one that he or she could attempt alone.
Anyone can attempt an Insight check. Proficiency is NOT required.
Another way to do this is that they do a a group roll (Basic Rules, p. 62) They all roll the dice. PC X gets one roll. The dice are against him either way.
To make a group ability check, everyone in the group makes the ability
check. If at least half the group succeeds, the whole group succeeds.
Otherwise, the group fails.
The point of the first part of this answer is that there are other ways to let the player's knowledge become verified during subsequent action during play. It is OK to let that be a problem for the player characters to deal with as they keep adventuring together. I recommend you use the slow reveal to overcome the mechanical messiness that comes with applying these die rolls to this instance of PvP. The core assumption (or conceit) of the game is that the party works together, each offering their own skills. All of the mechanics support this assumption.
Pick any of the above, you are the DM, but be aware of the shortcomings of the dice for these non-physical interactions.