What a PC believes shouldn't be determined by a dice roll.
Instead, give them clues depending on the results of their insight check. For instance, if the PCs are interrogating an NPC regarding a string of robberies, an Insight Check DC10 might allow the PCs to notice that the NPCs eyes widened when shown the torn scarf found at the mayor's house, despite him denying seeing it before (or do an opposed bluff vs insight if the NPC has a very good poker face).
This way, you can play with their perceptions a lot. Maybe the NPC they're talking to knows who this scarf belongs to... or maybe he just realized it was a set-up, as it was stolen from him a few days ago, but would rather deny everything in front of the PCs to take care of the matter himself.
Like in real-life, your players will have to decide what they do with the information available to them. If their Insight check is too low, you might give them only part of the information (the NPC seems to be very nervous, which really could mean anything...), which might in turn lead them to make the wrong decision.
This also seems to be suggested by the PHB (p.178) :
Insight :
Your Wisdom (Insight) check decides whether you can determine the true intentions of a creature, such as when searching out a lie or predicting someone’s next move. Doing so involves gleaning clues from body language, speech habits, and changes in mannerisms.
A good insight check should reveal these clues, but the interpretation should be left to the player.
To specifically address the situation of Insight vs. "Not bluffing", you can interpret the insight check as someone trying really hard to find clues about someone's lies. And when they search too hard, people always end up finding something... So if they roll too low, you could just give them wrong cues about the NPC's behaviour (he seems to be sweating a lot... but that's because he was running to get home before his wife sees her surprise birthday gift, which you don't tell them). As to what could be regarded as "too low", there is a very good guideline in the PHB (p.174) to help you set DCs for such tasks.
Typical difficulty classes
- 5 --- Very easy
- 10 --- Easy
- 15 --- Medium
- 20 --- Hard
- 25 --- Very hard
- 30 --- Nearly impossible
For example, if you think it would normally be very easy to spot someone's lie (Pureferret's example of a paladin whose very nature is against lies), the DC to notice they are speaking truthfully would be 5. On the other hand, if it would normally be hard to spot the lies (the guy from local fence is so used to lying that you can't really tell if he's lying or not anymore, whether you expect him to or not), then the DC should be 20.
As a DM, it is up to you to set up the DCs for such task. Even if the person isn't lying, success could give some behavioral clues to something else ("he looks distracted, as if he's preoccupied with something else") that could be, or not, a plot hook. On the other hand, failure wouldn't reveal any clues whatsoever, and you could rule that a failure by 5 or more (rolling 15 or under against a DC of 20, for example) leads to wrongful interpretation. For example, when dealing with the guy from the local fence, the PCs are expecting him to lie so much that everything seems to indicate it ("he's never looking at you in the eyes, and often checks down the alley behind you" -- of course! he's dealing with illegal goods and is checking for the town watch!).
Best Answer
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...
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.
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 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.
Your criteria include:
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.
OK, here we go.
Contests: should I use them?
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) ...
... 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
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.
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.