I once spent a year working for a manager who, although he was not a compulsive liar, could never say anything straight.
He'd phone in late and have to embellish the story from a plausible beginning to an implausible outcome.
He'd let down customers and we'd cringe as he would spin a tale to them over the 'phone that was clearly a lie.
He would explain his reasoning for a decision (which wasn't necessary as he was the manager) with evidence that he'd made up.
I think it becomes a habit to such people that when they learn they can lie, they do it all the time.
Instead of agents phoning and saying:
"It's dead quiet so I'm updating our records and seeing what research I can do at the same time and I think you're on the bench. Got time for a chat about the state of the market?"
"Our last CV for you was received over six months ago, if circumstances have changed, please send an update."
"I have a gig that, while not quite your cup of tea, is similar to what you do. I'm trying to find someone to fill the role, have you any suggestions of where I can look?"
"We're trying to break in <this > sector and you've worked there a lot. Can you give us any contacts at places with Preferred Supplier Lists so we can apply? And, if would you send us a CV highlighting your skills in <this> sector, we'll be trying to sell you into those organisations at the same time."
Instead of the above, they automatically think they must lie.
I can only think sales attracts liars and, as we know, recruitment tends to attract poor quality sales people. Hence we get calls from a succession of transparently bad, habitual, liars. And as an industry we tend to be smarter than average, it is often painfully obvious to us they are trying to deceive.