Reversed and remanded with instructions to grant the petition by published opinion. Judge MURNAGHAN wrote the opinion, in which Judge ERVIN joined. Senior Judge PHILLIPS wrote a dissenting opinion.
OPINION
MURNAGHAN, Circuit Judge:In 1981, Irving Hawkins was sentenced to fifty years of imprisonment in North Carolina as a habitual felon. After receiving contradictory notifications about when he would be eligible for parole, he was finally paroled in 1992. Hawkins successfully reintegrated into' the community, obeying all *269conditions of his parole, holding a job in which he was promoted, and reacquainting himself with his family. Then in 1994 he was rearrested on the basis that the determination that he was eligible for parole had been made in error.
Having exhausted his state appeals, Hawkins petitioned for habeas corpus relief. He argues primarily that his reinearceration violates the Fourteenth Amendment’s guarantee of substantive due process. We hold that, where the parolee did not know that his release was in error, his interest in his continued liberty crystallized during the two years of successful parole and the Fourteenth Amendment requires that we strictly scrutinize the State’s intentional infringement of that interest.
I.
The facts in this case are essentially agreed upon: the State does not contest Hawkins’s “apparent good-conduct while released,” and Hawkins concedes that, although he did not realize it at the time, he was statutorily ineligible when he was paroled.1 We begin with a short review of how Hawkins came to be arrested, paroled and rearrested.
On February 27,1981, Irving Hawkins was convicted in Guilford County, North Carolina, of possession, sale and delivery of one-half gram of cocaine. Hawkins was found to be a habitual felon and sentenced to fifty years of imprisonment on the sale and delivery charge and ten years concurrently on the possession charges (along with sixty days concurrently on a charge of driving under the influence). It must be admitted that Hawkins is not a sympathetic character. The habitual felon determination was based on evidence that Hawkins had as a young man been convicted of and imprisoned for one count of rape, two counts of aggravated assault with intent to commit rape and one count of armed robbery. See State v. Simmons, 56 N.C.App. 34, 286 S.E.2d 898, 900 (Ct.App.N.C.1982). His FBI record reveals other less serious charges as well, both as an adult and as a minor.
From the beginning of his incarceration as a habitual felon, Hawkins was given conflicting explanations of when he would be eligible for parole. The record suggests that, at first, he may have been told that he would be eligible for parole very shortly after his conviction. Then, on June 14, 1982, the Parole Commission informed Hawkins that he would not be eligible for parole until he had “served 30 years” of his sentence, giving him a parole eligibility date of “October 20, 2010.” The Commission assured Hawkins it had “studied all the facts in your case, and we are sure that we are following the requirement of the law” in reaching this 2010 date. About a year later, on September 7, 1983, the Parole Commission changed its mind once again: “After carefully checking your parole eligibility date, we find that you will not be eligible for parole until April 20, 2018.” Finally, on March 13, 1992, Hawkins was suddenly informed that he was being considered for community service parole. Assuring Hawkins that it had “made a careful investigation of this case,” the Parole Commission paroled Hawkins on July 6,1992.
Hawkins claims to have been completely rehabilitated during his eleven years of imprisonment. The magistrate judge who first heard this habeas petition found that Hawkins had a good prison record during those years and, while incarcerated, obtained a business degree from Shaw University through a study-release program. The magistrate judge further found that during Hawkins’s nearly two years on parole he substantially complied with his parole obligations, held a steady job in which he was promoted, *270and reestablished ties with his family. Although there is some indication that Hawkins did not complete the community service that he was assigned, the Parole Commission reported that “Hawkins had no problems while on parole,” and the State does not contest Hawkins’s statement in his affidavit that during his release he “never violated [his] parole.”
Then, on March 25, 1994, Hawkins was rearrested on the basis that he had not been eligible for parole in 1992. The Parole Commission concluded that the habitual felon statute under which Hawkins was sentenced, N.C. Gen.Stat. § 14-7.6, required that he serve 75% of his 50-year sentence (37.5 year's) before he would be eligible for parole. Ironically, that statute had been repealed effective only four months after Hawkins’s sentencing and replaced with a requirement that a habitual offender serve “not less than seven years.” By letter of October 10, 1994, the Commission informed the reincarcerated Hawkins that his “current parole eligibility date” would be April 20, 2018.
Hawkins challenged his reincarceration on various grounds. Having effectively exhausted his claims in state court,2 Hawkins on January 27, 1995, petitioned for habeas corpus relief. His claim therefore is subject to the pre-Antiterrorism and Effective Death Penalty Act standards. See Lindh v. Murphy, 521 U.S. 320, 117 S.Ct. 2059, 2063, 138 L.Ed.2d 481 (1997). A magistrate judge recommended that such relief be denied, and the district judge agreed with that recommendation, granting summary judgment to the State. Hawkins appeals to us.
II.
We review the district court’s grant of summary judgment to the State de novo. See Savino v. Murray, 82 F.3d 593, 598 (4th Cir.1996). Hawkins argues primarily that his reincarceration violated his substantive due process rights, and advances alternative theories of waiver, estoppel and the bar against installment sentences. He also argues that his parole revocation hearing did not contain all of the procedural protections he was due. Because we believe that the established principles of the substantive component of the Fourteenth Amendment’s Due Process Clause govern the case, we begin with an exposition of those principles.
A.
The Due Process Clause of the Fourteenth Amendment guarantees that no state shall “deprive any person of life, liberty, or property, without due process of law.” U.S. Const, amend. XIV. “Although a literal reading of the Clause might suggest that it governs only the procedures by which a State may deprive persons of liberty, for at least [111] years, since Mugler v. Kansas, 123 U.S. 623, 660-661, 8 S.Ct. 273, 31 L.Ed. 205 (1887), the Clause has been understood to contain a substantive component as well, one ‘barring certain government actions regardless of the fairness of the procedures used to implement them.’ ” Planned Parenthood v. Casey, 505 U.S. 833, 846, 112 S.Ct. 2791, 120 L.Ed.2d 674 (1992) (quoting Daniels v. Williams, 474 U.S. 327, 331, 106 S.Ct. 662, 88 L.Ed.2d 662 (1986)). Through the doctrine of substantive due process, “all fundamental rights comprised within the term liberty are protected by the Federal Constitution from invasion by the States.” Whitney v. California, 274 U.S. 357, 373, 47 S.Ct. 641, 71 L.Ed. 1095 (1927) (Brandéis, J., concurring), quoted in Planned Parenthood, 505 U.S. at 847, 112 S.Ct. 2791.
It is contested whether the asserted interest infringed by Hawkins’s reincarceration is such a fundamental liberty right. The Supreme Court has “regularly observed that the Due Process Clause specially protects those fundamental rights and liberties which are, objectively, ‘deeply rooted in this Nation’s history and tradition’ and ‘implicit in the" concept of ordered liberty,’ such that ‘neither liberty nor justice would exist if they were sacrificed.’” Washington v. Glucksberg, 521 U.S. 702, 117 S.Ct. 2258, 2268, 138 L.Ed.2d 772 (1997) (quoting Moore v. City of *271East Cleveland, 431 U.S. 494, 503, 97 S.Ct. 1932, 52 L.Ed.2d 531 (1977), (plurality opinion), Palko v. Connecticut, 302 U.S. 319, 325, 58 S.Ct. 149, 82 L.Ed. 288 (1937), and id. at 326, 58 S.Ct. 149) (citations omitted). Certain liberties enshrined in the Bill of Rights offer the clearest examples of those held to be “fundamental,” but the category is not limited to this list, nor is it limited to “those practices, defined at the most specific level, that were protected against government interference by other rules of law when the Fourteenth Amendment was ratified.” Planned Parenthood, 505 U.S. at 847, 112 S.Ct. 2791. Instead, the “full scope of the liberty guaranteed by the Due Process Clause” comprises “a rational continuum which, broadly speaking, includes a freedom from all substantial arbitrary impositions and purposeless restraints, and which also recognizes, what a reasonable and sensitive judgment must, that certain interests require particularly careful scrutiny of the state needs asserted to justify their abridgment.” Poe v. Ullman, 367 U.S. 497, 543, 81 S.Ct. 1752, 6 L.Ed.2d 989 (1961) (Harlan, J., dissenting from dismissal on jurisdictional grounds) (citations omitted), quoted in Planned Parenthood, 505 U.S. at 848-49, 112 S.Ct. 2791.
But substantive due process does not absolutely guarantee that these fundamental rights will be held inviolate. Executive action that infringes such a right violates the substantive component of the Due Process Clause “only when it ‘can properly be characterized as arbitrary, or conscience shocking, in a constitutional sense.’ ” County of Sacramento v. Lewis, 523 U.S. 833, 118 S.Ct. 1708, 1717 & n. 8, 140 L.Ed.2d 1043 (1998) (quoting Collins v. City of Harker Heights, 503 U.S. 115, 128, 112 S.Ct. 1061, 117 L.Ed.2d 261 (1992)). In the past, the Supreme Court has described the substantive due process doctrine as if it provided two independent types of protection: “So-called ‘substantive due process’ prevents the government from engaging in conduct that ‘shocks the conscience’ or interferes with rights ‘implicit in the concept of ordered liberty.’ ” United States v. Salerno, 481 U.S. 739, 746, 107 S.Ct. 2095, 95 L.Ed.2d 697 (1987) (quoting Rochin v. California, 342 U.S. 165, 172, 72 S.Ct. 205, 96 L.Ed. 183 (1952), and Palko, 302 U.S. at 325-26, 58 S.Ct. 149) (citations omitted)(emphasis added). However, the Court’s most recent foray into the realm characterizes the determination “whether the behavior of the governmental officer is so egregious, so outrageous, that it may fairly be said to shock the contemporary conscience” as a “threshold question,” “antecedent to” any “possibility of recognizing a substantive due process right to be free of such executive action.” County of Sacramento, 118 S.Ct. at 1717 n. 8. Therefore, not unless éxecutive action “shocks the conscience” does it reach the level of abuse of power necessary to invoke substantive due process protections for life, liberty or property. Id. at 1717 & n. 8.
Negligently inflicted harm, the basis of traditional tort liability, is not sufficiently conscience-shocking as to implicate constitutional Due Process Clause protections, whether substantive or procedural. See id. at 1718(citing Davidson v. Cannon, 474 U.S. 344, 348, 106 S.Ct. 668, 88 L.Ed.2d 677 (1986)). “Whether the point of the conscience-shocking is reached when injuries are produced with culpability falling within the middle range, following from something more than negligence but ‘less than intentional conduct, such as recklessness or “gross negligence,” ’ is a matter for closer calls.” Id. (quoting Daniels, 474 U.S. at 334 n. 3, 106 S.Ct. 662)(citations omitted). That is, “deliberately indifferent [official] conduct [is] enough to satisfy the fault requirement for due process claims” in certain circumstances, id. (giving as an example a state’s deliberate indifference to the medical needs of its prisoners, in violation of the Eighth Amendment), although in other circumstances such “[d]eliberate indifference ... may not be so patently egregious” as to constitute a.conscience-shocking abuse of power, id. 118 S.Ct. at 1718-19 (explaining that deliberate indifference to life is “less egregious” in the context of a high-speed law enforcement chase). Rather than negligence, recklessness or deliberate indifference, it has traditionally been intentional actions, those “deliberate decisions of government officials to deprive a person of life, liberty, or property,” *272about which the substantive component of the Due Process Clause is concerned. Daniels, 474 U.S. at 331, 106 S.Ct. 662, quoted in County of Sacramento, 118 S.Ct. at 1718. “[C]onduet intended to injure in some way unjustifiable by any government interest is the sort of official action most likely to rise to the conscience-shocking level.” County of Sacramento, 118 S.Ct. at 1718.
B.
Applying these principles to Hawkins’s case, our task is to determine whether the agreed-upon facts demonstrate that the State has intentionally violated a fundamental liberty interest, or has been deliberately indifferent to such an interest to an extent that shocks the conscience. If so, the State’s actions must be subjected to strict scrutiny. “[T]he Fourteenth Amendment ‘forbids the government to infringe ... “fundamental” liberty interests at all, no matter what process is provided, unless the infringement is narrowly tailored to serve a compelling state interest.’” Glucksberg, 117 S.Ct. at 2268(quoting Reno v. Flores, 507 U.S. 292, 302, 113 S.Ct. 1439, 123 L.Ed.2d 1 (1993)) (ellipsis in original); Herndon v. Chapel Hill-Carrboro City Bd. of Educ., 89 F.3d 174, 177 (4th Cir.1996), cert. denied, — U.S. -, 117 S.Ct. 949, 136 L.Ed.2d 837 (1997).
1.
The “threshold question” whether the behavior of the Parole Commission was sufficiently conscience-shocking as to implicate substantive due process protections at all is not at issue in this case, because the State acted intentionally to deprive Hawkins of his liberty. If the liberty interest that Hawkins asserts is a fundamental one protected by the Due Process Clause, then its deliberate violation by the State, unless narrowly tailored to serve a compelling interest, is an arbitrary abuse of power sufficient to shock the judicial conscience. See County of Sacramento, 118 S.Ct. at 1717-18. It need not have been the specific intent of the State to harm the individual, so long as the State acted “with full appreciation” of the effect of its action. Id. at 1718 n. 9. To state it more simply, the “fundamental rights” protected by substantive due process are those “ ‘implicit in the concept of ordered liberty’ such that ‘neither liberty nor justice would exist if they were sacrificed.’ ” Glucksberg, 117 S.Ct. at 2268(quoting Palko, 302 U.S. at 325, 326, 58 S.Ct. at 152). What kind of society would this be were we to condone any intentional infringement of fundamental rights so defined?
2.
This case therefore turns on whether the liberty interest asserted by Hawkins to prevent his reincarceration is a “fundamental” one. Whether a fundamental liberty interest exists is of course a legal determination, subject to de novo review. See Beverati v. Smith, 120 F.3d 500, 503 (4th Cir.1997). The Supreme Court has required a “careful description” of the asserted interest, Glucksberg, 117 S.Ct. at 2268, recognizing its “reluc-tan[ee] to expand the concept of substantive due process because guideposts for responsible decisionmaking in this unehartered area are scarce and open-ended,” Collins, 503 U.S. at 125, 112 S.Ct. 1061, quoted in Glucksberg, 117 S.Ct. at 2267. Such a liberty interest may be created by state law or by the Due Process Clause itself, see e.g., Washington v. Harper, 494 U.S. 210, 221-22, 110 S.Ct. 1028, 108 L.Ed.2d 178 (1990)(“We have no doubt that, in addition to the liberty interest created by the State’s Policy, respondent possesses a significant liberty interest in avoiding the unwanted administration of .antipsychotic drugs under the Due Process Clause of the Fourteenth Amendment.”), but judicial restraint requires us to “exercise the utmost care whenever we are asked to break new ground in this field,” Collins, 503 U.S. at 125, 112 S.Ct. 1061.
a.
Luckily, Hawkins does not ask us to break new ground here: the liberty interest that he asserts has already been recognized as a fundamental one, to which substantive due process protections attach, in two Fourth Circuit opinions as well as by a number of our sister circuits. A parolee’s interest in his continued liberty during good behavior is protected by the substantive due process *273right to the finality of his sentence. The Fourth Circuit has recognized this fundamental right in two contexts, in the cases of United States v. Lundien, 769 F.2d 981 (4th Cir.1985), and United States v. Cook, 890 F.2d 672 (4th Cir.1989). Each of these cases advances the proposition that it is fundamentally unfair and violates the guarantee of due process for a court to increase a sentence, even where correcting an unlawful sentence, once the defendant has served so much of the original sentence that “his expectations as to its finality have crystallized.” Lundien, 769 F.2d at 987; Cook, 890 F.2d at 675.3
In Lundien, the district court initially sentenced the defendant to a term of ten years on each of two counts, to be served concurrently, but five days later amended the sentence by increasing it to twenty years on one of the counts. See 769 F.2d at 982. The defendant challenged the amendment. After explaining that the Double Jeopardy Clause did not address the situation, the Fourth Circuit observed that it “seems more likely that any constitutional source for protection of the defendant’s interest in the finality of his sentence must be found in the fifth amendment’s guarantee of due process.” Id. at 986.4
The Circuit observed that the exact parameters of the guarantee of due process in this context were “not firmly fixed.” Id. at 987. However, it set forth the following principle, which applies to Hawkins’s case as well:
[D]ue process may also be denied when a sentence is enhanced after the defendant has served so much of his sentence that his expectations as to its finality have crystallized and it would be fundamentally unfair to defeat them. As the First Circuit has stated the principle:
[T]he power of a sentencing court to correct even a statutorily invalid sentence must be subject to some temporal limit. When a prisoner first commences to serve his sentence, especially if it involves a long prison term as here, the prospect of release on parole or otherwise may seem but a dimly perceived, largely unreal hope. As the months and years pass, however, the date of that prospect must assume a real and psychologically critical importance. The prisoner may be aided in enduring his confinement and coping with the prison regime by the knowledge that with good behavior release on parole or release outright will be achieved on a date certain. After a substantial period of time, therefore, it might be fundamentally unfair, and thus violative of due process for a court to alter even an illegal sentence in a way which frustrates a prisoner’s expectations by postponing his parole eligibility or release date far beyond that originally set.
Id. (quoting Breest v. Helgemoe, 579 F.2d 95, 101 (1st Cir.1978)) (emphasis added) (second alteration in original); see also United States v. Smith, 115 F.3d 241, 248 (4th Cir.) (recognizing in passing the rule of Lundien that due process may be denied if a sentence is enhanced after a defendant’s expectation of its finality has crystallized), cert. denied, — U.S. -, 118 S.Ct. 315, 139 L.Ed.2d 244 (1997).
The expectation of finality of sentence that arises merely from being given a parole date is much stronger in Hawkins’s case, where the defendant has actually been paroled, has no knowledge that his parole was in error, has made the difficult transition from prisoner to rehabilitated citizen, and has become a productive member of society. Once the defendant has been released on parole and has successfully reintegrated into society for a period of years, “his expectations as to [the] finality [of his release on parole] have crystallized and it would be *274fundamentally unfair to defeat them.” Lundien, 769 F.2d at 987.
The question arises, how long does it take for such an expectation to “crystallize?” In Lundien, the Fourth Circuit held that where the defendant “had served only five days of an expected sentence of ten years and he had not even reached his final prison destination,” his expectations had not sufficiently “crystallized.” Id. Breest, on which Lundien relied, held that 14 days was not long enough. See 579 F.2d at 98-101. Hawkins, however, was on parole for almost two years. Certainly his expectation of the finality of his parole determination crystallized within that time.
The Fourth Circuit reaffirmed the principle announced in Lundien in the case of United States v. Cook, 890 F.2d 672 (4th Cir.1989). There the Circuit recognized a court’s inherent power to correct a mistaken sentence. In doing so, it explained:
This inherent power is not without limitation, for at some point every sentence must become final. As we indicated in United States v. Lundien, 769 F.2d 981 (4th Cir.1985), it would be fundamentally unfair and a violation of due process to allow a district court to enhance a sentence “after the defendant has served so much of his sentence that his expectations as to its finality have crystallized.”
Id. at 675 (quoting Lundien, 769 F.2d at 987) (part of citation omitted). The Circuit therefore held that the power to correct “an acknowledged and obvious mistake” in sentencing “exists only during that period of time in which either party may file a notice of appeal. After that time, we believe that the sentence has become final, and the district court lacks any authority to modify it.” Id. If the Due Process Clause limits a court’s power to correct a mistake in sentencing to only the SO days in which an appeal may be taken, because after 30 days an inmate’s interest in the finality of his sentence has crystallized, then clearly the Parole Commission may not correct a mistake in its parole calculations two years after the defendant has been released without violating the same guarantee of due process.
Other Circuits and district courts have held that in certain circumstances it would be inconsistent with the fundamental principles of liberty and justice protected by the Due Process Clause to allow a state to reincarcerate an erroneously released prisoner after he has made a good adjustment to society. See, e.g., DeWitt v. Ventetoulo, 6 F.3d 32, 34-35 (1st Cir.1993); Johnson v. Williford, 682 F.2d 868, 873 (9th Cir.1982); United States v. Merritt, 478 F.Supp. 804, 807-08 (D.D.C.1979); Lanier v. Williams, 361 F.Supp. 944, 947 (E.D.N.C.1973). An instructive example is offered by the case of DeWitt v. Ventetoulo, 6 F.3d 32 (1st Cir.1993).
DeWitt had been sentenced to life imprisonment after conviction of a particularly evil assault with intent to murder. While serving his sentence, DeWitt came to the aid of a prison guard who was being attacked by an inmate and later testified for the state in the prosecution of the inmate. In recognition of these efforts, the trial court suspended all but 15 years of DeWitt’s life sentence. See id. at 33.
Two years later, the state supreme court held in a separate case that a trial court could not suspend such a sentence once a defendant had begun to serve it. Nevertheless, the state made no effort to undo the suspension of DeWitt’s sentence. Six years after his sentence had been partially suspended, DeWitt was granted parole and released from prison. Had DeWitt’s sentence not been suspended, he would not have been eligible for parole for another 16 months. See id.
After his parole, DeWitt obtained work and reestablished contact with his family. However, eight months after his release he was involved in an altercation for which he was arrested. Instead of seeldng to revoke his parole, the state vacated its earlier order that had suspended in part his life sentence. DeWitt was recommitted to serve the remainder of the term of life imprisonment. See id.
Reserving the question whether DeWitt had violated the conditions of his parole, the First Circuit held that due process notions of fundamental fairness prohibited the state from reimposing DeWitt’s original life *275term. See id. at 35-36. Citing the Fourth Circuit’s decision in Lundien, the First Circuit explained that only in extreme cases would a court’s correction of an earlier mistake in sentencing be “so unfair that it must be deemed inconsistent with fundamental notions of fairness embodied in the Due Process Clause.” Id. at 35. Without establishing any specific tests, the First Circuit proposed certain factors to which consideration should be given:
to the lapse of time between the mistake and the attempted increase in the sentence, to whether or not the defendant contributed to the mistake and the reasonableness of his intervening expectations, to the prejudice worked by a later change, and to the diligence exercised by the state in seeking the change.
Id.
In finding that DeWitt’s rearrest was fundamentally unfair, the First Circuit stressed that the state with due diligence could have challenged the suspension of his sentence far sooner than it did. See id. It also noted that DeWitt not only was led reasonably to believe that his sentence had been reduced for a number of years while in prison, but he was actually released, set down new roots in society, got a job and reestablished family ties. See id. Finally, the First Circuit noted that the state’s interest in rearresting De-Witt and correcting its earlier mistake was weak: it seemed to be an attempt to avoid granting DeWitt the full hearing necessary to revoke his parole. See id. at 35-36.
The First Circuit’s opinion in DeWitt supports our conclusion in Hawkins’s case. In explaining that its rule was a narrow one, the First Circuit described the numerous cases which have allowed a sentence to be increased after it was initially imposed in error. Each of these cases was distinguished from DeWitt’s:
In virtually all [such cases] that we have discovered, there has been some distinguishing circumstance that separates that case irom DeWitt’s, for example, because (as is often true) the defendant was still in prison, or the interval between the original sentence and its correction was brief, or because the defendant almost certainly knew or should have known that an error had been made.
Id. at 36. None of those circumstances distinguish DeWitt’s case from Hawkins’s, however: Hawkins was released from prison, the interval between his release and its correction was almost two years, and he did not know that his parole eligibility determination was erroneous. The First Circuit in DeWitt followed the statement in Lundien “that due process must in principle impose an outer limit on the ability to correct a sentence after the event.” Id. We do the same.
b.
The State seeks to avoid the principle of Lundien and Cook on three grounds. First, the State attempts to distinguish the two cases by arguing that, unlike Lundien and Cook, Hawkins’s sentence was not “enhanced” by the Parole Commission. That in those cases a mistaken sentence was increased, whereas in Hawkins’s ease his erroneously granted parole was revoked, is a distinction without a difference. In the case where a sentence being served is increased, making the parole date farther away, the inmate’s reasonable and significant expectation of future liberty has been frustrated, implicating the protection of the Due Process Clause. The frustration is the same, if not magnified, where, the parole date having passed and the inmate having been released, parole is unexpectedly revoked and the inmate is returned to prison, without any fault of his own, to continue serving a sentence. In both cases the inmate has an interest in the finality of the sentence imposed upon him by the state, including his date of eligibility for parole. See Lundien, 769 F.2d at 987. Once that interest crystallizes, the substantive guarantees of the Due Process Clause prevent the state from infringing it.
Second, the State tries to distinguish Lun-dien and Cook by arguing that Hawkins had no “reasonable expectation” of remaining on parole release because he had been “on notice at least since 1982 he had to serve 30 years before [he would be] eligible for parole.” See Green v. Christiansen, 732 F.2d 1397, 1399 (9th Cir.1984) (refusing to estop the government from reincarcerating an er*276roneously released prisoner who had not been so misled as to form a reasonable expectation of release, and who was therefore charged with constructive knowledge that he still had time to serve). This is the State’s key argument: that Hawkins knew from letters he received from the parole commission that he had at least 30 more years to serve before he would be eligible for parole, and therefore he had actual or constructive notice that his parole was in error. The State repeats this argument, almost word-for-word, no fewer than fourteen separate times in its brief.
Despite the State’s insistent repetition, the argument is meritless. The State misrepresents the record when it claims that Hawkins was “advised at the beginning of his sentence in 1982 and again in 1983 that he would not be eligible for parole until he served more than 30 years of his sentence.” In fact, the letters to which the State refers contradicted each other, setting parole eligibility dates that were eight years apart. Throughout his sentence, Hawkins was notified of as many as four different dates on which he would be eligible for parole. First, there is evidence that he was told that he would be eligible for parole quite shortly after his imprisonment; second, the Parole Commission sent a letter to correct that earlier information, explaining that they were now “sure,” after “stud[ying] all the facts” in his case, that he would be eligible for parole in 2010; third, he was told that after “carefully checking,” the Parole Commission found he would not be eligible for parole until 2018; and fourth he was told the Parole Commission had decided after “careful investigation” that he was eligible for parole (and was in fact paroled) in 1992. The Parole Commission had repeatedly revised its conclusion about when he would be eligible for parole, and three times those conflicting revisions were accompanied by assurances that, this time, the Commission had been “careful[]” and was “sure.” When Hawkins received the fourth revision, indicating that he was in fact eligible for parole, he had no reason to believe that any of the earlier notices were more accurate.
From Hawkins’s perspective, the earlier parole eligibility calculations were superseded by the latest one. And the fact that he was actually paroled confirmed to him that the most recent letter was accurate. Finally, after almost two years on parole during which he was supervised by a North Carolina state-government parole officer, he must reasonably have had every confidence that he had put his days in prison behind him.
It is important to note that while the State argues that Hawkins had notice that his parole was in error, it does not claim that he had actual knowledge of the error. Hawkins stated in his affidavit: “I was not aware at any time prior to [the date of parole] that I was not eligible for parole when I was, in fact, paroled, nor was I aware that the parole commission made a mistake when paroling me until my arrest in March, 1994.” The State does not contest this assertion. The petitioner’s lack of actual knowledge that his release was in error is what distinguishes Hawkins’s case from eases such as Camper v. Norris, 36 F.3d 782, 784-85 (8th Cir.1994) (finding no due process violation where the defendant knew his continued release was in error), and United States v. Martinez, 837 F.2d 861, 864-66 (9th Cir.1988)(holding that incarceration after a delay of many years did not violate the due process guarantees of the Fifth Amendment where the defendant knew that a mistake had been made).
However, the State maintains that Hawkins should be presumed to have known that he was ineligible for parole. After all, it is a truism that all citizens are presumed to know the law. See, e.g., Jacobson v. United States, 503 U.S. 540, 550, 112 S.Ct. 1535, 118 L.Ed.2d 174 (1992); United States v. Aquino-Chacon, 109 F.3d 936, 938 (4th Cir.), cert. denied, — U.S. -, 118 S.Ct. 335, 139 L.Ed.2d 260(1997). Given this presumption, the State argues that “[n]o person obtains a right to incorrect application of a statute,” citing Lustgarden v. Gunter, 779 F.Supp. 500, 506 (D.Colo.1991), aff'd, 966 F.2d 552(10th Cir.1992). If the State’s argument is correct, then a defendant cannot have a fundamental liberty interest in the finality of a sentence that is contrary to law.
But both Lundien and Cook foreclose the argument in this context. In Cook, the Fourth Circuit recognized that “at some *277point every sentence must become final.” 890 F.2d at 675 (emphasis added). We affirmed that it would be “fundamentally unfair and a violation of due process to allow a district court to enhance a sentence” once it had crystallized, even where the original sentence was the result of “an acknowledged misinterpretation of the pertinent [sentencing] guidelines section.” Id. We then applied that rule to a sentence that “was not authorized by [the pertinent sentencing guidelines] section nor based on a departure from the guidelines,” in short, a “sentence [that] was not a lawful one.” Id. We made no contention that the defendant’s interest in the finality of his unlawful sentence was illegitimate because he should be presumed to know the law. By contrast, we held that the district court had the power to correct the sentence only “[b]ecause the time for the government to file a notice of appeal had not expired,” and the sentence had therefore not become “final.” Id.
Lundien also explicitly rejected the argument that the Due Process Clause does not afford an interest in a statutorily invalid sentence. Those words, quoted above, bear repeating:
[T]he power of a sentencing court to correct even a statutorily invalid sentence must be subject to some temporal limit.... After a substantial period of time, therefore, it might be fundamentally unfair, and thus violative of due process for a court to alter even an illegal sentence in a way which frustrates a prisoner’s expectations by postponing his parole eligibility or release date far beyond that originally set.
769 F.2d at 987 (quoting Breest, 579 F.2d at 101) (internal quotation marks omitted) (alteration in original) (emphasis added).
The rule that all persons must be presumed to know the law certainly applies where an individual takes actions that violate the law, but claims that he was ignorant of the law’s proscription. That presumption is a reflection of the principle that ignorance of the law is no excuse for its violation. But the presumption is inapposite in this sentencing context — here, the prisoner is entitled to expect that the sentence that he is given will be final, and after a period of time his expectation crystallizes. We do not require a prisoner independently to analyze the sentencing guidelines and their interactions with the parole eligibility rules to determine for himself whether the sentencing judge’s or Parole Commission’s decisions are correct. The tangle of repealed and amended, interdependent sentencing and probation provisions in North Carolina has caused confusion for its Parole Commission and Attorney General before, see generally Glenn v. Johnson, 761 F.2d 192 (4th Cir.1985), and we very much doubt that Hawkins, without any legal training, could be expected to untangle them.
The State’s third attempt to avoid the rule of Lundien and Cook is by citing two cases, Glenn v. Johnson, 761 F.2d 192 (4th Cir.1985), and Crowley v. Landon, 780 F.2d 440 (4th Cir.1985), which, it claims, stand for the proposition that “the state’s interest in correctly enforcing its laws can outweigh a prisoner’s settled expectation of continued release on eironeous parole.” But these cases simply do not address the due process claim made by Hawkins.
In Glenn v. Johnson, the Fourth Circuit addressed the proper interpretation of a North Carolina parole eligibility statute. The Parole Commission believed that Glenn and other similarly situated prisoners would be eligible for parole after serving ten years of their sentence; the state Attorney General believed otherwise. See 761 F.2d at 193-94. A class of such prisoners litigated the issue, and the Fourth Circuit concluded that the Parole Commission’s interpretation was in error. See id. at 194-95.
However, the opinion did not resolve whether the Due Process Clause would be implicated if Glenn had been informed at first of the earlier parole date and then, after his expectations of parole crystallized, told that the later date was correct. In fact, the Fourth Circuit specifically declined to address “considerations of alleged due process ... infractions,” explaining that “[t]hose questions, while fascinating, need not long engage us” because the Circuit found that the statute had “inescapably]” prescribed the proper parole date all along. Id.
*278The State asserts that “Glenn stands for the proposition that the Parole Commission has, and indeed must have, authority to correct error in determining parole eligibility even when the correction upsets a prisoner’s settled expectation of earlier release.” However, despite the State’s claim, there is no indication in the Glenn opinion that the prisoner had been led to rely on, or even informed of, the erroneous, early parole eligibility date and then later been told that another date was correct. Because Glenn specifically declined to address any due process considerations it is not controlling in our case, and certainly it cannot counter the rule of Lundien and Cook.
The State also relies upon Crowley v. Landon, in which the Fourth Circuit addressed the case of three inmates whose sentences had been suspended and who had been released on supervised probation by a Virginia trial court. Following unfavorable publicity, the Virginia attorney general petitioned the Supreme Court of Virginia for a writ to bar the inmate’s release. Eventually, the Supreme Court of Virginia reversed the trial court and vacated the release orders. The inmates voluntarily surrendered and were reincarcerated. See 780 F.2d at 442.
The inmates petitioned for habeas corpus relief from their reincarceration. Although their situation posed similar due process concerns as does Hawkins’s ease, the Crowley petitioners did not argue that reincarceration violated their substantive due process rights. Rather,they made only the following four arguments:
The petitioners’ habeas petition attacks their reincarceration on the grounds that: 1) it deprived them of equal protection under the fourteenth amendment of the United States Constitution [because other released prisoners were not reincarcerat-ed]; 2) they have a due process right to good time credit towards parole for the time spent on probation; 3) their reincar-ceration violated the constitutional protection against ex post facto laws; and, 4) their reincarceration subjected them to cruel and unusual punishment.
Id.
The Fourth Circuit denied each of these four asserted bases for habeas relief.5 The State is wrong, therefore, when it asserts that “Crowley stands for the proposition that the state may reincarcerate one group of prisoners who were erroneously released while choosing not to pursue others without violating due process or equal protection.” The court in Crowley was not presented with and did not answer the due process question posed in our case.
In sum, Fourth Circuit law provides that after an inmate is sentenced, his reasonable expectation of future release on a specific date crystallizes over time. Once crystallized, that reasonable expectation of freedom is a legitimate liberty interest protected by the Due Process Clause. When Hawkins was released on parole and reintegrated himself into the community, he reasonably expected to continue to live as a free citizen so long as he obeyed the conditions of his parole. During the two years in which he was on parole without violation, that interest crystallized. When the state rearrested Hawkins to correct its two-year-old error, it *279violated his right to due process of law.6
3.
It remains only strictly to scrutinize the State’s actions to determine whether its violation of Hawkins’s substantive due process right was narrowly tailored to serve a compelling interest. The State has a broad interest in the effective enforceméht of its laws, including the correction of its legal errors, so as to guarantee to its citizens a predictable and consistent governance. The State also has an interest in reincarcerating an erroneously released inmate to serve the entirety of his sentence as originally imposed for specific and general deterrent, retributive and rehabilitative reasons. See N.C. Gen. Stat. § 15A-1340.12 (“The primary purposes of sentencing a person convicted of a crime are to impose a punishment commensurate with the injury the offense has caused, taking into account factors that may diminish or increase the offender’s culpability; to protect the public by restraining offenders; to assist the offender toward rehabilitation and restoration to the community as a lawful citizen; and to provide a general deterrent to criminal behavior.”).
These interests are significantly weakened in Hawkins’s case, and his rearrest is not narrowly tailored to serve them. It is far too late for the sentencing provision to be effectively enforced so as to provide a consistent rule of law. The State’s interest would have been better served by a competent determination of when Hawkins would be eligible for parole in the first place. The Parole Commission’s continually-shifting-yet-eontin-ually-confident determinations aré not at all well-tailored to the effective enforcement of sentencing provisions.
If there were an allegation that the State had an interest in-reincarcerating Hawkins to protect the public safety because Hawkins had not been rehabilitated, that interest would certainly be compelling and reincar-ceration at this late date might be narrowly tailored to remedy the continuing, threat to the public. But the State does not assert such an interest, conceding Hawkins’s good behavior for the two years he was on parole. The Parole Commission exercised its discretion to parole Hawkins in 1992, noting that he had “made some effort to improve his situation while in prison, via a college degree” and opining that “the best interests of the public and of the inmate will be served by his release under supervision at this time.” Since his release he has successfully reintegrated into the community and substantially complied with all parole obligations, vindicating the Parole Commission’s judgment that he was a good candidate for parole. There is no evidence nor claim that Hawkins poses any future danger to the community.
The State’s interest in general deterrence will not be significantly undermined if Hawkins is allowed to remain on parole. It is inconceivable that any individual who knows that the law proscribes his conduct and that it establishes a particular penalty for violation will be less deterred from breaking the law because he believes that if he is caught, convicted and sentenced the Parole Commission may erroneously parole 'him too early, and thereafter he will not be rearrested. The rearrest of Hawkins is not narrowly tailored to serve any real interest in general or specific deterrence.
The State’s interest in retribution is similarly weak. Hawkins long ago completed his sentences for the crimes that underlay his adjudication as a habitual felon. And the *280statute that prohibited Hawkins’s parole until he had served 75% of his sentence, N.C. Gen.Stat. § 14-7.6, has long since been repealed. Only four months after Hawkins’s sentencing, it was replaced with a requirement that such a habitual offender serve at least seven years of his sentence;7 Hawkins served about eleven years before his parole, and has served four more since his rearrest. His punishment has been more than “commensurate with the injury ... caused” by his sale and delivery of the half gram of cocaine. Whatever interest the State still has in seeing him punished further is overwhelmed by his crystallized interest in the finality of his parole.
In fact the State’s interest in the rehabilitation of this prisoner is likely to be substantially harmed by his reincarceration for another two decades of imprisonment. He has demonstrated that he can function as a law-abiding and productive member of society. If he is returned to parole, he will still be governed by the threat of reinternment should he violate any parole requirements. But this long reincareeration will likely not improve a rehabilitation that has already been achieved, and may in fact only discourage and embitter him, by teaching that the government cannot be relied upon to treat its citizens fairly.
In sum, North Carolina’s two-year-old recognition of its error comes too late. The State’s violation of Hawkins’s rights guaranteed by the substantive component of the Due Process Clause cannot survive strict scrutiny.
III.
Other courts have examined the due process interests at stake in regards to an erroneously released inmate through the doctrines of estoppel, see, e.g., Green, 732 F.2d at 1397 (refusing to estop the government from rearresting an inmate with constructive knowledge that his release was mistaken); Johnson, 682 F.2d at 871-73 (estopping the government from rearresting an erroneously paroled inmate), of waiver, see, e.g., Camper, 36 F.3d at 784 (finding no waiver where the state’s actions were mere negligence, not an affirmative wrong, and where the defendant knew his continued release was in error); Lanier, 361 F.Supp. at 947 (holding that the state had waived its right to rearrest the petitioner where it had led him, through no fault of his own, to believe that he was free of a prison sentence and made no attempt for a number of years to reacquire custody over him), and of the prohibition against the imposition of sentences in installments, see, e.g., Merritt, 478 F.Supp. at 806-08 & n. 6 (recognizing “the principle that a prisoner is protected by due process from being required to serve his sentence in installments,” and holding that the state’s rearrest of an erroneously released prisoner would be inconsistent with fundamental principles of liberty and justice). Hawkins argues that he is entitled to habeas corpus relief on these alternative grounds. Because we find that the substantive guarantees of the Due Process Clause have been violated directly, we do not address the issues of estoppel, waiver or the prohibition of installment sentences.
Hawkins further argues that his reincarceration violated his right to procedural due process because he was not allowed at his parole-revocation hearing to introduce evidence about his “difficult but successful adjustment to civilian life during his time on parole.” But Hawkins did have an opportunity, albeit a limited one, to make these arguments at his parole revocation hearing. In any case, to the extent that the argument is not about the process afforded to him, but about the substantive basis of the State’s decision to revoke his parole, it is a concern of substantive due process discussed above. To the extent that Hawkins argues that Morrissey v. Brewer, 408 U.S. 471, 92 S.Ct. 2593, 33 L.Ed.2d 484 (1972), requires additional procedural protections when the State wishes to revoke erroneously granted parole, the argument is barred by Teague v. Lane’s prohibition against the creation of new procedural rules on habeas corpus review, 489 U.S. 288, 310, 319, 109 S.Ct. 1060, 103 *281L.Ed.2d 334 (1989).8
IV.
The substantive component of the Fourteenth Amendment’s Due Process Clause includes a right to the finality of a criminal sentence, once that sentence has crystallized, as described by the Fourth Circuit in Lun-dien and Cook. Where a parolee is unaware that his parole has been granted erroneously, and reasonably so, and where he successfully reintegrates himself into the community and substantially complies with all of his parole obligations for two years, his fundamental liberty interest in the finality of the parole decision has crystallized. By intentionally depriving Hawkins of this fundamental liberty interest, the North Carolina Parole Commission abused its power to a degree that shocks the conscience, violating Hawkins’s right to substantive due process. The decision to the contrary of the district court is, therefore,
REVERSED AND REMANDED WITH INSTRUCTIONS TO GRANT THE PETITION.
. We expressed some concern at oral argument about how the evidence about Hawkins’s rehabilitation had gotten into the record, as it appeared to have been based on the Parole Commission’s report of the parole revocation hearing rather than on state court findings of fact or a federal court evidentiary hearing. Because there are no state court findings of fact to presume correct, we would typically assume the truth of Hawkins’s attestations for purposes of deciding the appeal from summary judgment, see Turner v. Jabe, 58 F.3d 924, 930 n. 6 (4th Cir.1995), and would remand to the district court to hold an evidentiary hearing if those facts established that Hawkins was entitled to relief. However, the State assured us that it did not contest the facts put forth by Hawkins, and that no remand for further fact-finding was necessary.
. The State has waived the exhaustion requirement for Hawkins’s main claim of a substantive due process violation.
. Lundien and Cook's recognition of a sentencing court's inherent authority to correct an erroneous sentence has been superseded by Fed. R.Crim.P. 35(c), which "in effect codifies the result in [Cook and a similar Second Circuit case] but provides a more stringent time requirement.” Fed.R.Crim.P. 35 advisory committee notes, 1991 amendment.
. Although Lundien examined substantive due process protections under the Fifth Amendment, the same analysis applies to the Fourteenth Amendment, "given the Supreme Court's essentially identical interpretations of the concept [of 'liberty'] under the two amendments.” Piechowicz v. United States, 885 F.2d 1207, 1214 n. 9 (4th Cir.1989).
. The closest Crowley came to addressing whether an erroneously released defendant had any protections against rearrest was when it cited United States v. Merritt, 478 F.Supp. 804, 807 (D.D.C.1979), in a footnote to the portion of the opinion denying good time credit toward parole for the months the petitioners had spent on release. See 780 F.2d at 444 n.6. The Fourth Circuit explicitly declined to decide whether to adopt Merritt's conclusion that three factors would have to be present to warrant habeas relief:
The erroneous release must not have been attributable to the petitioner, the action of the authorities must have amounted to more than simple neglect, and reincarceration must be unequivocally inconsistent with fundamental principles of liberty and justice.
Id. The Fourth Circuit merely noted that the Crowley petitioners’ case fell "far short” of meeting Merritt's requirements. Id. In Merritt, the petitioner had been released on parole for nearly three years before his rearrest on an outstanding detainer, and he had previously unsuccessfully sought to clarify the status of the detainer; in Crowley, the three petitioners had been out of prison for only seven, six and two months, during which their release orders were being challenged.
. It may be argued that Hawkins has not been injured, but rather has received a windfall by his release: after all, if he had been asked up-front whether he would prefer to serve his full sentence uninterrupted or to serve it with a two year period of release in the middle, he would likely have chosen the latter. But it is unjust for the government to parole an inmate and allow him to believe that he may begin his life anew, and then after he has proven himself rehabilitated by holding down a job, reestablishing family ties and integrating successfully in the community for two years, to rearrest him and claim the parole was in error. Hawkins is deeply injured by the fracturing of the family ties he has striven to reestablish, by the interruption of the career he has begun, and by the destruction of the new life he has made for himself, all in reliance, for two years, on the Parole Commission’s determination. "Even convicted criminals are entitled to be treated by their government in a fair and straightforward manner.” Johnson, 682 F.2d at 872.
. That provision, too, has since been replaced.
. The State’s claim that all of Hawkins’s arguments are new rules and thus barred by Teague is meritless. The application of the substantive due process holdings of Lundien and Cook to this new set of facts is not the creation of a new rule. And Teague only prohibits the imposition of new procedural rules on habeas, see Bousley v. United States, 523 U.S. 614, 118 S.Ct. 1604, 1610, 140 L.Ed.2d 828 (1998), of which category Hawkins's substantive due process claim is not a member.