A woman is thought to have been murdered (corrected this first sentence from a previous comment). A man is arrested for it. He is offered a plea bargain deal that will get him 15 years or he can take his chances in court but would get life if found guilty. All they have is circumstantial evidence but the arrested man is convinced by his lawyer to plea bargain due to the overwhelming circumstantial evidence against him. (side-note: For this scenario, the man did NOT actually murder this woman as we find out later in this story but he just didn't want to take the chance of getting sentenced to life in prison). Man serves his 15 years and is released...no probation, he served his entire sentence. Knowing he did not murder this woman he looks for her after he is released and finds her. Ends up she wanted to disappear and start a new life and set this man up to be framed for her murder. He is obviously mad at this woman and after he finds her, he kills her for revenge of sending him to prison and losing 15 years of his life for something he didn't do. He is arrested again and admits to the police to killing her but does not worry about being charged for murder because he has already been convicted of her murder and served his sentence. Can he be charged, convicted and sent to prison again?
Yes, because the crimes are different instances. Let's remove the guilty plea and the fact that it is murder: can a person assault a person, be tried and imprisoned, then assault the same person later – and get off by declaring "Double jeopardy!". No, it's not the same crime. It's the same type of crime, and involves the same victim, but it is still a different crime. The same with your proposed scenario. (Incidentally, your first line is wrong: the woman wasn't murdered, she was thought to have been murdered).
This is the premise of the movie Double Jeopardy (1999), and it has already been debunked by Alan Dershowitz (among others):
Mr. DERSHOWITZ: No. It wouldn't work at all. Look, any lawyer could make the argument--25 years ago, I appealed a case and I actually won it. A guy tried to shoot somebody who he thought was alive, but was actually dead. And the court ruled that man dies but once and acquitted my man of murder charges. But today, the law on double jeopardy has become very restrictive. It has to be the same transaction. The same event. It even has to be in the same state.
Can he be charged, convicted and sent to prison again?
No, it would be illogical. It turns out that your assumption about plea bargain preempts prosecution of the actual murder.
The premise of "different crimes" is a non-sequitur because a person can be murdered no more than once. Thus, any and all sets of specific facts about a murder of a person are (can only be) one and the same set of facts, regardless of whether or not the prosecutor got it/them right the first time.
Now, "a plea bargain itself is contractual in nature and 'subject to contract-law standards'", Baker v. United States, 781 F.2d 85, 90 (1986) (citations omitted). Insofar as a contract where a mistake "was made as to a basic assumption", "the contract is voidable by the adversely affected party unless he bears the risk of the mistake". See Restatement (Second) of Contracts at § 151(1). Here it is irrefutable the adversely affected party is only the defendant: He got sentenced and imprisoned for the alleged murder of a woman who actually was alive.
Moreover, the mistake or risk of mistake was not defendant's. The defendant's decision on the plea bargain does not fit the alternative terms outlined in the Restatement at § 154(a) and (b). For instance, rather than representing to the prosecutor that he committed murder, the defendant merely agreed to waive his rights in a way that both (1) benefited the prosecutor, and (2) is in line with the prosecutor's demand(s). It is unlikely for the character of the plea bargain to be such as "neither you [defendant] nor I [prosecutor] are sure 'who' murdered her, but let's just assume you [defendant] did it".
At all times the defendant was aware that he did not commit the murder for which he was imprisoned pursuant to the plea bargain. This precludes the scenario of defendant's "limited knowledge" formulated in Restatement at § 154 (b).
The only possibility is that the court could disrupt the tenets of contract law under pretext of Restatement at § 154 (c), although that would be speculative and de facto imply double jeopardy because the defendant already served his time in prison. Indeed, it is explained that "[j]eopardy 'attaches' when [...] a plea is accepted" (please note that the Wikipedia page cites Crist v. Bretz, 437 U.S. 28 (1978), although I admittedly have not thoroughly read the opinion so as to pinpoint that assertion more precisely).
Consequently, the exchange of considerations in that contract and the defendant's compliance therewith forfeit the People's option to subsequently prosecute the murder of that specific woman (because, as aforesaid, murder can happen no more than once per victim).