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. (In contrast, my son rarely lies, probably not because of superior moral fiber, but because he's such a transparently bad liar!)
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 it 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. There's a reason previous generations spent so much time and effort explicitly teaching values (even if their methods were sometimes questionable). We as adults might roll our eyes, but I've heard my children directly refer to stories like "the boy who cried wolf" when reminding each other to be honest.