Let me break this into two questions:
Is it ok to lie to the players ...
Yes, but ...
Your role as DM is nicely summarised in the How to Play section:
The DM describes the environment.
The players describe what they want to do.
The DM narrates the results of the adventurers’ actions.
Since you are the one and only window the players have into the game, you should endeavour to make that window as transparent as possible. The players can only interact with the environment through their characters and those characters are not omniscient (usually), so it's ok if your description of the environment incorporates the limits of the characters' knowledge. However, it's not ok to deliberately misrepresent things that are or should be within the scope of the characters' understanding.
In summary, it's ok if the environment lies - it's not ok if the DM lies about the environment.
... rolling an insight
Ok, now we are talking about action resolution - the quasi-step in between:
The players describe what they want to do.
The DM narrates the results of the adventurers’ actions.
So, let's take a look at how we got here: what did "[t]he players describe [as] what they want to do"?
If it was "I want to know if he's lying" well then the appropriate response is "Well, I want more money and less body mass. How are you going to get what you want?" The thing about action resolution is that the player must actually state an action that can be resolved, not just state a wish about how they would like things to be.
The Angry GM says (and I agree) than an action needs both an intent ("I want ...") and an approach ("... by doing ..."). This gives you, the DM, the two pieces of information you need to resolve the action: the results if the player succeeds and the knowledge to assess if the action will succeed (no die roll needed), won't succeed (no die roll needed) or might succeed (die roll needed).
Let me illustrate how this works:
Player: "I want the orc dead [intent], by hitting it with my battle axe [approach]."
As a DM, you need to look at this to see if it will succeed (e.g. the orc is currently unconscious at the player's feet), won't succeed (e.g. the orc is 200 feet away behind a wall) or might succeed (e.g. normal melee combat). The resolution is either "the orc is dead" or "the orc is not dead" - the second has some nuances that the orc might be closer to being dead than it was before if the character hit and did some damage but not enough to kill the orc but those are mere details.
Finding the truth is no different from any other action the players might attempt:
Player: "I want to determine if he's lying or not by ...
- ... looking for inconsistencies in his story."
- ... questioning him about what he knows about the paladin and seeing if that matches what I know."
- ... questioning the others and seeing if they tell the same story."
- ... calling him a liar and taking out the tongue remover tongs and heating them in the fire."
- ... buddying up to him to gain his confidence."
These all have the same outcome. If successful, the player knows whether the person is lying or telling the truth, if unsuccessful, they don't know or, at least, they don't know more than they knew before.
Success can be automatic, impossible or require an ability check. The approach determines what ability check to use - most are Wisdom (Insight) but I've also included approaches that use Charisma (Intimidation) and Charisma (Persuasion).
Remember we are resolving the action, the appropriate ability and proficiency come from HOW the players are doing it, not WHAT they are trying to do. Making the orc dead by hitting them with an axe uses a different ability than using a bow or a spell. Similarly, learning the truth can use a different ability depending on the approach.