They could have evolved with lies, developed the tech, then branched off into honesty later.

That makes no sense either. Evolution means that this change happened gradually over the time. However the moment you have a group which is always honest and believes you and group which is allowed to lie, then the lying group will take over the honest group. To lie and manipulate is a massive advantage.