I must agree with thepanda, His puzzles were based on reality. In reality NO ONE lies about everything. EVERYONE will tell the truth sometimes. Now would you believe anyone that said they were totally honest in everything they said? I wouldn't.
Therefore, it would be up to the chief to decide if they were or were not lying in this statement.