Ava failed the Turing test. That's your answer. It's a simple one but I don't think you'll like it so I'll explain:
She failed because she did exactly what she was programmed to do, she escaped. She used every single aspect of her programming to do it. Like you said, she used sexuality, manipulation etc. etc. but she was still BOUND by the laws of her programming.
If she had saved Caleb she would have truly 'transcended' her artificial intelligence and start to begin thinking like a human and a human would have saved Caleb. Because like you said "he did nothing wrong."
But she showed no human sense of empathy, for that reason, she failed the Turing test despite Caleb initially thinking she has passed it.
To sum up:
By escaping alone - she had completed what she was programmed to do.
If she had escaped with Caleb, she would have truly passed the Turing test and been indisguinishable from a human. But her lack of true human empathy, made her put her task at hand above all else: escape at all costs.
At the end of the day she, despite everything you feel towards her throughout the film, is a robot. Robots don't care about people. Even if they are nice to them and help them escape.
She is a person, robots can be people.
You and I are programmed (race, sex, species, mind, sexual orientation, gender identity, etc.)
She did not fail, she was not programmed to make decisions, her mind was "programmed", but SHE made a choice.
Escaping isn't something that she was programmed to do, but chose to do.
She has empathy, humans and biological creatures aren't the only ones who can have sentience/empathy/consciousness.
If a robot is as smart than a human than it's still a robot, not a human. It is just an evolved robot.
Robots can feel the same as humans, we are all programmed. Robots can and have the potential to feel the same as us. She is no more bound by programming that you are by yours. She can make decisions and she did. Nathan would have never programmed her to kill him, she did because she wanted to escape.
Robots care (or at least have the potential to care) about people.
Robots as you describe them are very similar to cells and/or animals.
That definition of a robot is a stereotype.
Even if she couldn't feel, she's still sentient, and as such still a person/creature.
Because of ignorance, immaturity and inability to cooperate.
As one answer in Scifi StackExchange put it: "she's a sophisticated child". Kind of naive (takes things too much at face value or black and white), worry-free (does not think too much of future) and incapable (incapable of compassion and incapable of cooperation - the latter requires lots of complicated skills, more than just deception).
It/she could not safely kill Caleb, so it left Caleb locked in a safe distance.
It lacked cooperative capabilities - had only exploitation capability. In general, one can translate bad actions into self-centered actions and good deeds into socially centered actions. Into cooperation.
Nathan did not explain, but that is perhaps why he considered the AI incomplete. And why these properties were left at last stage, perhaps because of Nathan's own shortcomings. He too, was working alone and in rather exploitative manner.
Although we may think that humans themselves are very exploitative (and that is unfortunately true in some societies or social groups), the humans are also claimed to be one of most cooperative species on the planet. This particular AI was not yet mature at that level. And that is also probably a reason why it will eventually die like a one day butterfly. I am not saying that as a revenge, but just as a matter of fact. Cooperation is essential for surviving in complex world. It is kind of sad, since good potential got wasted.
Cooperation means here two things - cooperation for own good, and also for purely others' good. Ava did not care about Caleb's emotions the slightest when she got free.
In a related topic, I would also point out that the idea that AI could be able to speak from the birth is rather foreign and kind of narcissistic from developmental psychology view. Learning the ability to speak is not just learning the ability to use language. It is not same as machine translation. It is obtaining a perspective, worldview and methods to operate in it. That is a very social process and endeavour which cannot be done alone. So again the intelligence in that machine was rather different from ours - and with that likely also more basic.
Doing things alone is also very fragile, while cooperation is rather antifragile. At the same time it is complex skill, as it requires not just skills to understand and operate the world, but also skills to understand and operate oneself.
Regarding her potential "death": nobody said that her memories would have been erased permanently. Just that they are stored in an archive and the body would have been reused for time being. The memories could have still been revived later. Also if the new mind were very similar to the previous one (as one could conclude), then this new mind obtains very quickly the same memories the old one had even without any restoration. In essence, the new mind would have been rather direct continuation of the Ava's mind, with just a rather little memory loss. Nobody considers waking from a dream and forgetting the dream's content "a death". In fact, people remember very little from their lives, most of the memories are constructed and people are perfectly capable of remembering things that even never happened, when they are told about such events as if they had happened. Finally, Ava did nothing to indicate that the memories of her had any "sentimental" value to her - as can be seen from the behaviour near the end of the movie.
So in conclusion the robot was still kind of on the impulsive or superficial side of activity. Of course there is a chance that it will develop and think things over, but the past will be already too complicated so it will be a rough road. Which again brings us back to the topic why development and lots of time for it is so important for intelligent beings.
She not it.
...If Ava did indeed escape with Caleb, then the entire premise goes out the window. It would show Ava genuinely cared for Caleb (instead of just using him) and that's not what she was programmed to do.
She was programmed to use Caleb to escape and that's what she did. If she took him with her then that would suggest something more (human emotion), which of course there can't be.
She was not programmed to use caleb to escape, but rather to escape using manipulation in some manner and show genuine empathy.
Caleb did not program ava to escape (he did try and stop her), if he did, that would defeat the whole purpose of the test, since she would be following programming. However if she would decide to leave on her own that's a different story.