My daughter, a few years older than yours, is also a skillful liar when she chooses to be.  My best advice is "trust but verify."  Children are good at knowing what works, and if lying is a reliable, consequence free way of getting what she wants, there's no reason --from her point of view --not to deploy it.

At this point, I think my daughter has digested the lesson that gaining a reputation for lying results in the natural consequence being given a diminished amount of trust, which I think has helped.  If you know there's a consistent pattern of lies, and you still fall for every time, the problem is really yours, not hers.

Although I don't believe you can change a person's underlying personality, I do believe that virtues and values are very learnable.  The mistake is to believe that children will just pick those up naturally, without either being taught them explicitly or experiencing the consequences of not practicing them.