If we evolved ever more complex ways of lying, then we must also have evolved ever more complex ways of detecting lies.

Good point. Of course, that mechanism is for detecting other people's lies, and there is some evidence that it's specific to ideas and/or people you already disagree with or are suspicious of... meaning that increased intelligence doesn't necessarily relate.

One of the central themes in the book I'm working on is that brains are much better at convincing themselves they've thought things through, when in actuality no real thinking has taken place at all.

Looking for problems with something you already believe is a good example of that: nobody does it until they have a good enough reason to actually think it through, as opposed to assuming they already did it, or not even noticing what it is they believe in the first place.