Well, usually when there's a mass problem, some technology eventually eliminates it.

Like cars making horse manure in cities a non-issue (https://www.youtube.com/watch?v=w61d-NBqafM)

Maybe the solution to everybody lying would be some way to directly access a person's actual memories from their brains..