HOLMES, Circuit Judge.

Petitioner-Appellant Richard S. Fairchild, currently on death row in the State of Oklahoma, appeals from the District Court for the Western District of Oklahoma's denial of his petition for writ of habeas corpus filed pursuant to 28 U.S.C. § 2254. Mr. Fairchild was convicted in an Oklahoma state court of child abuse murder and sentenced to death. For the reasons stated below, we hold that Mr. Fairchild's ineffective assistance of counsel claim is unexhausted and that the district court should determine in the first instance whether it is appropriate to stay and abate the action on the petition in order to give Mr. Fairchild an opportunity to exhaust this claim. Accordingly, we VACATE the district court's judgment and REMAND to the district court to make the stay-and-abeyance determination and to conduct further proceedings consistent with this opinion. We do not reach the merits of Mr. Fairchild's other appellate claims.

I. BACKGROUND

We presume that the factual findings of the state court are correct. 28 U.S.C. § 2254(e)(1). Thus, we recite the facts developed by the Oklahoma Court of Criminal Appeals ("OCCA") and present additional facts as they become pertinent. See generally Fairchild v. State (Fairchild I), 998 P.2d 611 (Okla.Crim.App. 1999).

In November 1993, Mr. Fairchild was living with Stacy Broomhall and her three children in Midwest City, Oklahoma. Id. at 615. On November 13, 1993, Mr. Fairchild and Ms. Broomhall drank beer most of the afternoon and evening. Mr. Fairchild consumed approximately twelve beers between 2:00 p.m. and 9:00 p.m. Id. That evening, they drove to Ms. Broomhall's mother's house in north Oklahoma City and continued to drink. Id. By the time they were ready to leave, Mr. Fairchild and Ms. Broomhall were too intoxicated to drive, so Ms. Broomhall's seventeen-year-old sister, Charity Wade drove them home. Id. Ms. Wade had intended to spend the night at Ms. Broomhall's house. But she decided not to do so after Mr. Fairchild made a sexual advance toward her. Instead, Ms. Wade put Ms. Broomhall's three children to bed and called a taxi to take her home. Id. While Ms. Wade waited outside for the cab, Mr. Fairchild retrieved a baseball bat and told her that, "if someone other than a cab driver came to pick her up, he was going to beat him to death." Id. When Ms. Wade left in the cab, some time before 10:30 p.m., Ms. Broomhall's three-year-old son Adam was asleep in his own bed. Id. at 615-16.

Roughly three hours later, Adam woke up crying and got out of bed. Id. His mother was asleep, and Mr. Fairchild told Adam to "hush it up." Id. at 616. When Adam persisted, Mr. Fairchild hit him several times, rupturing the inside of his upper lip and his left eardrum, and he held Adam's chest and then buttocks against a hot wall heater causing severe second-degree grid-patterned burns. Id. Mr. Fairchild told a detective several days later, "I think I pushed him up against the heater and held him up there," and, "The more he screamed, the more I just kept on hitting him." Id. When Mr. Fairchild threw Adam against the drop-leaf dining table, he stopped breathing. Id.

Mr. Fairchild woke Ms. Broomhall and called 911. Id. Adam was rushed to the hospital, but the head injury had caused severe hemorrhaging and swelling, and he died later that morning, never having regained consciousness. Id. Examination indicated that Adam had sustained approximately twenty-six blows to his body, including several to his head. Id. In a written statement to the police, Mr. Fairchild claimed that Adam was running in the house and "ran right into the table." Id.

Mr. Fairchild was convicted by an Oklahoma County jury of one count of first degree murder pursuant to Okla. Stat. tit. 21, § 701.7(C) (1991), and the trial court entered judgment on February 2, 1996. At the sentencing phase of the trial, the jury found that the murder was especially heinous, atrocious, or cruel and recommended imposition of the death penalty. Mr. Fairchild appealed his conviction and sentence to the OCCA, which, in 1998, affirmed, "[f]inding no error warranting reversal or modification." Fairchild v. State, 965 P.2d 391 (Okla.Crim.App. 1998). In 1999, the OCCA issued a superseding opinion reaching the same conclusion with somewhat different reasoning. Fairchild I, 998 P.2d at 615. In 2000, the OCCA denied Mr. Fairchild's application for post-conviction relief. Fairchild v. State (Fairchild II), No. PC-98-31, slip op. at 17 (Okla.Crim.App. Oct. 25, 2000).

On May 16, 2002, Mr. Fairchild sought habeas relief pursuant to 28 U.S.C. § 2254. The district court denied the petition on all grounds on September 26, 2006. Mr. Fairchild timely filed a notice of appeal. The district court granted a certificate of appealability ("COA") with respect to five issues: (1) whether the jury instructions failed to adequately explain the possible sentence of life without possibility of parole; (2) whether application of Oklahoma court decisions regarding the applicable mens rea for child abuse murder violates the Fourteenth Amendment; (3) whether Oklahoma's mens rea requirement for child abuse murder violates the Eighth Amendment; (4) whether the exclusion of lesser included or lesser related offense instructions violated federal rights; and (5) whether trial or appellate counsel provided ineffective assistance of counsel. Mr. Fairchild also seeks a COA for his claim of cumulative error. For the reasons noted below, we address only Mr. Fairchild's last issue, which is predicated upon the alleged ineffectiveness of his trial counsel, and we deny his request for a COA concerning alleged cumulative error as moot.

II. DISCUSSION

A. Standard of Review

Our review of a petition for writ of habeas corpus is governed by the Antiterrorism and Effective Death Penalty Act of 1996 ("AEDPA"). House v. Hatch, 527 F.3d 1010, 1015 (10th Cir. 2008), cert. denied, ___ U.S. ___, 129 S.Ct. 1345, 173 L.Ed.2d 613 (2009). If the state court adjudicated the claim on the merits, a petitioner is entitled to habeas relief only if he can establish that the decision was "contrary to, or involved an unreasonable application of, clearly established Federal law, as determined by the Supreme Court of the United States," 28 U.S.C. § 2254(d)(1), or was "based on an unreasonable determination of the facts in light of the evidence presented in the State court proceeding." Id. § 2254(d)(2); see, e.g., Hale v. Gibson, 227 F.3d 1298, 1309 (10th Cir. 2000).

In ascertaining whether the law is clearly established, we review Supreme Court holdings extant when the state court conviction became final. House, 527 F.3d at 1015 (quoting Williams v. Taylor (Terry Williams), 529 U.S. 362, 380, 120 S.Ct. 1495, 146 L.Ed.2d 389 (2000)). If a law "announces a rule that breaks new ground or imposes a new obligation on the States of [sic] the Federal Government," it is not clearly established. Id. (alterations and internal quotation marks omitted) (quoting Terry Williams, 529 U.S. at 381, 120 S.Ct. 1495). "[F]ederal courts may no longer extract clearly established law from the general legal principles developed in factually distinct contexts." Id. at 1017 n. 5. Finally, whether the law is clearly established is "dispositive" of the § 2254(d)(1) analysis. Id. at 1017. Specifically, only if we determine that the law is clearly established do we inquire whether the state court decision is either contrary to or an unreasonable application of that law. Id. at 1018.

"A state-court decision is contrary to clearly established federal law if: (a) `the state court applies a rule that contradicts the governing law set forth in Supreme Court cases'; or (b) `the state court confronts a set of facts that are materially indistinguishable from a decision of the Supreme Court and nevertheless arrives at a result different from [that] precedent.'" Id. (alteration in original) (quoting Maynard v. Boone, 468 F.3d 665, 669 (10th Cir. 2006)). "A decision is an `unreasonable application' of clearly established federal law only if the state court identifies the correct governing legal principle from the Supreme Court's decisions but unreasonably applies that principle to the facts of the prisoner's case." Young v. Sirmons, 486 F.3d 655, 663 (10th Cir. 2007) (internal quotation marks omitted). We presume the factual findings of the state courts to be correct, and petitioner bears the burden of rebutting this presumption by clear and convincing evidence. 28 U.S.C. § 2254(e)(1). We review the district court's legal analysis of the state court decision de novo. Young, 486 F.3d at 663.

When the state court did not determine the issue on its merits, and the district court decided the issue in the first instance, we review de novo the district court's conclusions of law. We review its findings of facts for clear error. Cummings v. Sirmons, 506 F.3d 1211, 1221-22 (10th Cir. 2007), cert. denied, ___ U.S. ___, 128 S.Ct. 2943, 171 L.Ed.2d 872 (2008); see also Cargle v. Mullin, 317 F.3d 1196, 1212 (10th Cir. 2003) (noting that in such circumstances, we are "not constrained by the deference principles in § 2254(d)"). We undertake this review cognizant that "our duty to search for constitutional error with painstaking care is never more exacting than it is in a capital case." Mitchell v. Gibson, 262 F.3d 1036, 1063 (10th Cir. 2001) (alterations and internal quotation marks omitted) (quoting Kyles v. Whitley, 514 U.S. 419, 422, 115 S.Ct. 1555, 131 L.Ed.2d 490 (1995)).

B. Ineffective Assistance of Counsel

Mr. Fairchild argues that he was denied effective assistance of counsel in violation of the Sixth Amendment by trial counsel's "failure to investigate and develop for the jury the defense that Mr. Fairchild was impaired not only by alcohol but by organic brain damage." Aplt. Opening Br. at 12. He argues that trial counsel prematurely chose and presented the simplistic case that Mr. Fairchild was a "mean drunk" when he should have developed the significance of "organic frontal lobe brain injury." Id. at 16, 20. Mr. Fairchild contends that, in light of the facts at his disposal, counsel instead should have requested testing by a neuropsychologist and then made his brain injuries the "centerpiece of the mitigation case." Id. at 20. He argues that, at the very least, he is entitled to an evidentiary hearing to more fully develop his claim.

Ineffective assistance of counsel claims are reviewed under the two-part test of Strickland v. Washington, 466 U.S. 668, 104 S.Ct. 2052, 80 L.Ed.2d 674 (1984), whereby the defendant must show that: (1) "counsel's representation fell below an objective standard of reasonableness," and (2) "there is a reasonable probability that, but for counsel's unprofessional errors, the result of the proceeding would have been different." Id. at 688, 694, 104 S.Ct. 2052. We approach these issues with "a strong presumption that counsel's conduct falls within the wide range of reasonable professional assistance," and that "the challenged action might be considered sound trial strategy." Id. at 689, 104 S.Ct. 2052 (internal quotation marks omitted). Nevertheless, "we are also conscious of the overwhelming importance of the role mitigation evidence plays in the just imposition of the death penalty." Mayes v. Gibson, 210 F.3d 1284, 1288 (10th Cir. 2000). In order to "insure the sentencing jury makes an individualized decision while equipped with the `fullest information possible concerning the defendant's life and characteristics,' [we] must scrutinize carefully any decision by counsel which deprives a capital defendant of all mitigation evidence." Id. (quoting Lockett v. Ohio, 438 U.S. 586, 603, 98 S.Ct. 2954, 57 L.Ed.2d 973 (1978)).

Before we reach the merits of Mr. Fairchild's ineffective assistance claim, however, he must clear several procedural obstacles. First, the OCCA gave two reasons for rejecting Mr. Fairchild's claim. It determined that Mr. Fairchild "[did] not establish deficient performance of counsel." Fairchild II, No. PC-98-31, slip op. at 10. But it also concluded that, as a procedural matter, he had waived the issue by failing to raise it on direct appeal. Id. Therefore, we must consider whether the issue is procedurally defaulted. Second, we must determine whether Mr. Fairchild properly requested an evidentiary hearing before the district court. Third, under AEDPA, with very stringent exceptions not relevant here, a state prisoner will not be entitled to an evidentiary hearing if he failed to exercise due diligence in developing the factual basis for his claim in the state courts. 28 U.S.C. § 2254(e)(2). Only after deciding whether Mr. Fairchild can surmount these obstacles, may we consider whether trial counsel was deficient.

1. Procedural Default

"Claims that are defaulted in state court on adequate and independent state procedural grounds will not be considered by a habeas court, unless the petitioner can demonstrate cause and prejudice or a fundamental miscarriage of justice." Smith v. Workman, 550 F.3d 1258, 1274 (10th Cir. 2008), petition for cert. filed, ___ U.S.L.W. ___ (U.S. July 9, 2009) (No. 09-5266); see also Smallwood v. Gibson, 191 F.3d 1257, 1268 (10th Cir. 1999). "A state procedural default is `independent' if it relies on state law, rather than federal law." Smith, 550 F.3d at 1274. "A state ground will be considered adequate only if it is `strictly or regularly followed' and applied `evenhandedly to all similar claims.'" Smallwood, 191 F.3d at 1268 (quoting Duvall v. Reynolds, 139 F.3d 768, 797 (10th Cir. 1998)). The state bears the burden of proving the adequacy of a procedural bar as it is "undoubtedly in a better position to establish the regularity, consistency and efficiency with which it has applied [its own rules] in the past." Hooks v. Ward, 184 F.3d 1206, 1217 (10th Cir. 1999).

In denying Mr. Fairchild's application for post-conviction relief, the OCCA concluded that he had waived his claim of ineffective assistance of trial counsel by failing to raise it on direct appeal. Fairchild II, No. PC-98-31, slip op. at 8. Under Oklahoma law, "[t]he only issues that may be raised in an application for post-conviction relief are those that . . . [w]ere not and could not have been raised in a direct appeal." Okla. Stat. tit. 22, § 1089(C). Although Mr. Fairchild produced numerous medical records, the OCCA found that the evidence did not establish "that these matters were not investigated by trial counsel or direct appeal counsel." Fairchild II, No. PC-98-31, slip op. at 8 (emphasis omitted). It concluded that Mr. Fairchild had failed to explain why he did not pursue an ineffective assistance claim on appeal. Therefore, the claims were deemed waived.

"We have . . . repeatedly questioned whether this Oklahoma procedural rule, requiring ineffective assistance of counsel claims to generally be brought on direct appeal, `can be deemed adequate and independent to bar habeas review.'" Young v. Sirmons, 551 F.3d 942, 956 (10th Cir. 2008) (quoting Cummings, 506 F.3d at 1224), petition for cert. filed, ___ U.S.L.W. ___ (U.S. July 23, 2009) (No. 09-5483). A state law requiring ineffective assistance claims to be brought on direct appeal can potentially infringe on a defendant's Sixth Amendment right to counsel. Kimmelman v. Morrison, 477 U.S. 365, 378, 106 S.Ct. 2574, 91 L.Ed.2d 305 (1986) ("Because collateral review will frequently be the only means through which an accused can effectuate the right to counsel, restricting the litigation of some Sixth Amendment claims to trial and direct review would seriously interfere with an accused's right to effective representation."). However, there is no "rigid constitutional rule" requiring states to allow ineffective assistance of counsel claims to be raised for the first time in a post-conviction proceeding. English v. Cody, 146 F.3d 1257, 1262-63 (10th Cir. 1998). Rather, if a state requires an ineffective assistance claim to be brought on direct appeal, the state's procedures must satisfy the so-called " Kimmelman imperatives." Id. at 1263. First, the state must "allow[] petitioner an opportunity to consult with separate counsel on appeal in order to obtain an objective assessment of trial counsel's performance." Id. (citing Kimmelman, 477 U.S. at 378 n. 3, 106 S.Ct. 2574). Second, the state must "provid[e] a procedural mechanism whereby a petitioner can adequately develop the factual basis of his claims of ineffectiveness." Id.

In limited circumstances, the OCCA can remand a case on appeal for an evidentiary hearing to allow the defendant to introduce evidence of counsel's deficient performance. Under OCCA Rule 3.11, a defendant may request an evidentiary hearing "[w]hen an allegation of the ineffective assistance of trial counsel is predicated upon an allegation of failure of trial counsel to properly utilize available evidence or adequately investigate to identify evidence which could have been made available during the course of the trial." Okla. Stat. tit. 22, ch. 18, app., Rule 3.11(B)(3)(b). However, we have been skeptical of whether Rule 3.11 is sufficient to satisfy the second Kimmelman imperative. "Oklahoma rarely, if ever, remands cases for such a hearing." Snow v. Sirmons, 474 F.3d 693, 726 n. 35 (10th Cir. 2007) (upholding the procedural default despite our "continuing concerns regarding Oklahoma's procedural bar to claims regarding the ineffectiveness of counsel"). Therefore, we have held that

the Oklahoma bar will apply in those limited cases meeting the following two conditions: trial and appellate counsel differ; and the ineffectiveness claim can be resolved upon the trial record alone. All other ineffectiveness claims are procedurally barred only if Oklahoma's special appellate remand rule for ineffectiveness claims is adequately and evenhandedly applied.

English, 146 F.3d at 1264; see also DeLozier v. Sirmons, 531 F.3d 1306, 1330 (10th Cir. 2008), cert. denied, ___ U.S. ___, 129 S.Ct. 2058, 173 L.Ed.2d 1138 (2009).

Here, Mr. Fairchild did have a new attorney on appeal. However, his claim — that counsel failed to investigate and present potentially mitigating evidence — is one that usually will require an evidentiary hearing. A court cannot reliably determine whether counsel's investigation was deficient without knowing what was investigated, and the scope of the investigation can rarely be discerned from the trial record. Nor is it possible to determine from the bare trial record whether counsel's choice of mitigation evidence was the result of a conscious, strategic decision. See Mayes, 210 F.3d at 1289 ("In the absence of an evidentiary hearing we can only speculate as to counsel's motivations."). In this case, these considerations are fully applicable. We conclude that Mr. Fairchild's ineffective assistance claim could not be resolved on the trial record alone.

Significantly, the State has failed to carry its burden of proving that Rule 3.11 is adequately and evenhandedly applied. The state bears the initial burden of pleading the procedural bar as an affirmative defense. Hooks, 184 F.3d at 1217. Once it has done so,

the burden to place that defense in issue shifts to the petitioner. This must be done, at a minimum, by specific allegations by the petitioner as to the inadequacy of the state procedure. The scope of the state's burden of proof thereafter will be measured by the specific claims of inadequacy put forth by the petitioner.

Id. Mr. Fairchild has raised several specific challenges to Rule 3.11. In particular, he claims that the rule is inadequate because it "requires an appellant [to] show more than would be required to prevail under Strickland," in that it requires ineffectiveness to be proven by clear and convincing evidence. Aplt. Opening Br. at 38. He also claims that the rule places defendants "in an extraordinarily difficult if not impossible situation" by requiring counsel to conduct an extra-record investigation without "provid[ing] any additional time for fact development." Id. at 37-38.

However, we need not decide whether Mr. Fairchild's challenges to the procedure are well-taken or, if they are, whether they would render Rule 3.11 inadequate to satisfy the second Kimmelman imperative. The State has failed to offer any meaningful arguments or evidence in response to Mr. Fairchild's claims. Although its brief gives abbreviated treatment to the procedural bar question, the State seems to rely on only the initial two conditions of the English test (i.e., relating to the presence of different counsel on appeal and a claim resolvable on the trial record). See Aplee. Br. at 27. Since it is undisputed that Mr. Fairchild had a different attorney on appeal, we must assume that the State's particular focus is on the requirement that the claim be resolvable based upon the trial record alone. We have already concluded, however, that the trial record is insufficient in this case. Therefore, the State has not carried its burden of establishing that its procedural bar — relating to the presentation of ineffective assistance claims on direct appeal — is an adequate and independent ground precluding habeas relief.

2. Preservation of the Request for an Evidentiary Hearing

Mr. Fairchild is required to properly request an evidentiary hearing in the district court, because we ordinarily do not decide issues raised for the first time on appeal. See McLuckie v. Abbott, 337 F.3d 1193, 1200 n. 3 (10th Cir. 2003). The district court rejected the request for an evidentiary hearing that appeared in Mr. Fairchild's habeas petition, which generically sought a hearing "as to the Petition as a whole and particularly as to any issues which involve facts not apparent from the existing record and to any issues which involve facts disputed by the state." R., Vol. I, Doc. 15, at 104 (Pet. for Writ of Habeas Corpus, filed May 16, 2002). The district court held that Mr. Fairchild's petition failed to present the specific allegations necessary to determine whether a hearing could substantiate Mr. Fairchild's ineffective assistance claims and merit habeas relief. However, by the time the district court ruled on the habeas petition, Mr. Fairchild also had submitted a more specific motion for an evidentiary hearing on the ineffective assistance of counsel claims. See R., Vol. I, Doc. 20, at 1-2 (Renewed Mot. for Evidentiary Hr'g and Br. in Supp., filed June 8, 2002) (noting that "[t]here is substantial evidence, not presented at trial, that indicates that Mr. Fairchild has suffered repeated head injuries" and that "a hearing would further show[] there was no informed tactical or strategic reason not to investigate, develop, and present this evidence"). Yet the district court had denied it "[b]ecause the parties have not completed their briefing of the legal issues and the record is not complete at this time, [so] the court cannot yet determine if an evidentiary hearing will be required." R., Vol. I, Doc. 21 (Dist. Ct. Order, filed July 11, 2002). We conclude that the combination of this motion and the request for an evidentiary hearing in the habeas petition was sufficient to alert the district court with adequate specificity to Mr. Fairchild's grounds for seeking an evidentiary hearing concerning ineffective assistance. Accordingly, in our view, Mr. Fairchild preserved his contention of error concerning the district court's denial of an evidentiary hearing and it is properly before us.

3. AEDPA Standard for an Evidentiary Hearing

Under AEDPA, a federal habeas court may not grant an evidentiary hearing to a defendant who failed to develop his claim in state court, except in a few, narrowly defined circumstances that are not at issue here. See 28 U.S.C. § 2254(e)(2); Young, 486 F.3d at 679. But "if the petitioner did not fail to develop the factual basis of his claim in State court, . . . a federal habeas court should proceed to analyze whether a hearing is appropriate or required under pre-AEDPA standards." Young, 486 F.3d at 679 (alterations and internal quotation marks omitted). Failure to develop the claim means a "lack of diligence, or some greater fault" on the petitioner's part. Williams v. Taylor (Michael Williams), 529 U.S. 420, 432, 120 S.Ct. 1479, 146 L.Ed.2d 435 (2000). "Diligence . . . depends upon whether the prisoner made a reasonable attempt, in light of the information at the time, to investigate and pursue claims in state court." Id. at 435, 120 S.Ct. 1479; cf. Allen v. Zavaras, 568 F.3d 1197, 1202-03 (10th Cir. 2009) (holding that a federal habeas petitioner who filed his state petition in the state Supreme Court, where review is discretionary, rather than the district court, where review is mandatory, had failed to exhaust all available state remedies).

Although not an absolute prerequisite, a petitioner typically must request an evidentiary hearing in state court. Michael Williams, 529 U.S. at 437, 120 S.Ct. 1479 ("Diligence will require in the usual case that the prisoner, at a minimum, seek an evidentiary hearing in state court in the manner prescribed by state law."). We have sometimes found such a request, by itself, to be sufficient proof of diligence. See Cannon v. Mullin, 383 F.3d 1152, 1176 (10th Cir. 2004) (citing examples). But requesting an evidentiary hearing does not "ipso facto satisf[y] the diligence requirement." Id. To determine diligence, we look to a petitioner's efforts to develop facts in compliance with state law. See Barkell v. Crouse, 468 F.3d 684, 694 (10th Cir. 2006) (holding that if petitioner "complied with what reasonably appeared to be the established state-law requirements, he cannot be said to have failed to develop the factual basis of his claim, even if his reasonable interpretation of state law turned out to be wrong" (alterations, citations and internal quotation marks omitted)). "But whether a habeas petitioner has shown `a lack of diligence' . . . is a question of federal law decided by the federal habeas courts." Boyle v. McKune, 544 F.3d 1132, 1136 (10th Cir. 2008), cert. denied, ___ U.S. ___, 129 S.Ct. 1630, 173 L.Ed.2d 1011 (2009).

There is a strong argument that Mr. Fairchild was not diligent. He did not present his ineffective assistance claim on direct appeal, as Oklahoma law generally requires. In his state post-conviction proceeding, he presented the claim and supported it with documentary evidence, including medical records. But as explained more fully below, the evidence he presented at this stage was far less specific and probative than evidence he later sought to present in federal court. He has not explained why he did not submit to the state court the best evidence which presumably would have been available to him — affidavits from a psychiatrist and psychologist who personally examined him.

However, the State has not argued that Mr. Fairchild was less than diligent. See Wilson v. Sirmons (Wilson I), 536 F.3d 1064, 1079 (10th Cir. 2008) (citing the State's failure to claim a lack of diligence as a relevant factor), aff'd, Wilson II, 577 F.3d at 1300, 2009 WL 2623336, at *14. The State did challenge Mr. Fairchild's diligence in its response to the district court. R., Vol. I, Doc. 27, at 102-04 (Resp. to Pet. for Writ of Habeas Corpus, filed Aug. 5, 2002). But it has effectively abandoned the argument by failing to make it in its appellate brief. See Allen, 568 F.3d at 1199 n. 3 ("We do not consider the issues raised by Allen in his original filing. By not including those issues in his supplemental brief, Allen has abandoned them."); see also Bronson v. Swensen, 500 F.3d 1099, 1104 (10th Cir. 2007) ("[W]e routinely have declined to consider arguments that are not raised, or are inadequately presented, in an appellant's opening brief."); Artes-Roy v. City of Aspen, 31 F.3d 958, 960 n. 1 (10th Cir. 1994) (holding that claims and arguments that are not "specifically address[ed]" on appeal are deemed to be abandoned). Therefore, we find that the State has forfeited reliance on Mr. Fairchild's neglect in not submitting the doctors' affidavits and will proceed as if Mr. Fairchild had been diligent in the presentation of his ineffective assistance claim.

4. Trial Counsel's Ineffectiveness

We finally reach the merits of Mr. Fairchild's claim. We have "consistently held [that] in a capital case the attorney's duty to investigate all possible lines of defense is strictly observed." Mayes, 210 F.3d at 1289 (internal quotation marks omitted); see Wilson I, 536 F.3d at 1084 ("[T]he question is not whether counsel did something; counsel must conduct a full investigation and pursue reasonable leads when they become evident."). According to Strickland, "strategic choices made after thorough investigation of law and facts . . . are virtually unchallengeable." 466 U.S. at 690, 104 S.Ct. 2052. However, "strategic choices made after less than complete investigation are reasonable precisely to the extent that reasonable professional judgments support the limitations on investigation." Id. at 690-91, 104 S.Ct. 2052. We noted in Smith v. Mullin, 379 F.3d 919 (10th Cir. 2004), that the ABA standards consider mental health evidence "of vital importance to the jury's decision at the punishment phase," holding that it was "patently unreasonable for [trial counsel] to omit this evidence from his case for mitigation." 379 F.3d at 942 (internal quotation marks omitted) (addressing evidence of mental retardation, brain damage, and troubled background); see also Terry Williams, 529 U.S. at 396, 120 S.Ct. 1495 (citing the ABA Standards for Criminal Justice as a guide to what constitutes adequate performance); Strickland, 466 U.S. at 688-89, 104 S.Ct. 2052 (same).

This is not a case where counsel completely failed to put on a mitigation case. Counsel developed two major themes during the second stage of trial: (1) Mr. Fairchild loses control of himself when he is drunk, and (2) the jury should be merciful because Mr. Fairchild's life still has value. But counsel never suggested that Mr. Fairchild's loss of control could be the result of organic brain damage. The list of mitigating factors presented to the jury said nothing about brain damage, referencing only drug and alcohol problems. See Trial R., Vol. IV at 613, 756 (stating that Mr. Fairchild "had serious drug and alcohol addictions," that "absent such addictions, this never would have happened," and that he "knows he is responsible for Adam Broomhall's death, but does not remember the act itself due to an alcoholic blackout"). Mr. Fairchild argues that the information available to trial counsel contained numerous indicators pointing to physical brain damage that would have provided a better explanation of his behavior. He contends that the failure to even investigate this possibility constitutes ineffective assistance of counsel.

As already mentioned, before we can determine whether counsel's investigation was deficient, we must first know what he investigated. Neither the district court nor the state courts have conducted an evidentiary hearing, and Mr. Fairchild has not submitted an affidavit by trial counsel. Only in the most exceptional circumstances will we issue the writ without allowing counsel an opportunity to explain his conduct. Nothing in this case would justify such an extraordinary step. Therefore, the pertinent question is whether to remand the case to the district court for an evidentiary hearing. We review a district court's denial of a motion for an evidentiary hearing for abuse of discretion. Coronado v. Ward, 517 F.3d 1212, 1217 (10th Cir.), cert. denied, ___ U.S. ___, 129 S.Ct. 134, 172 L.Ed.2d 102 (2008).

In determining whether to grant Mr. Fairchild's request for an evidentiary hearing, it is necessary to distinguish between the ineffectiveness claim that he raised in his state application and the claim he raised in his federal habeas petition. While Mr. Fairchild has consistently argued that counsel's failure to investigate was constitutionally deficient performance, we conclude that the substance of the claim he presented in federal court differs materially from that which he presented in state court. Before the OCCA, Mr. Fairchild argued that trial counsel was ineffective in failing to investigate his history of drug use, head injuries, and amateur boxing. Although Mr. Fairchild claimed that he was "cognitively impaired" in ways that "affected his judgment and reduced his culpability," he did not allege any particular impairments. R., Application for Post-Conviction Relief, at 17-18, 21 (Okla.Crim. App., filed Mar. 16, 1998). In his federal habeas petition, however, Mr. Fairchild presents a very different, far more specific, claim. He argues that counsel failed to appreciate the significance of Dr. Smith's diagnosis that Mr. Fairchild suffered from an acute brain syndrome and he failed to order additional neuropsychological testing. See R., Vol. I, Doc. 15 at 71 ("The report [of Dr. Smith] included something that counsel was not looking for: Mr. Fairchild suffered a severe chronic organic impairment. Counsel spent little or no time with Dr. Smith and did not discuss his finding of chronic organic damage." (citation omitted)); id. at 80 (noting that "a lawyer cognizant of the available evidence of organic brain damage, including that reflected in Dr. Smith's report, would have been in a strong position to refute the prosecution's implications that Mr. Fairchild did not have anything organically wrong with him, that Mr. Fairchild simply chose to drink"). We conclude that Mr. Fairchild has failed to exhaust this far more specific and powerful claim because he never presented it to the OCCA.

As to the claim Mr. Fairchild raised in state court, the OCCA determined that Mr. Fairchild had failed to present sufficient evidence to prove that trial counsel had not investigated the potentially mitigating evidence. Mr. Fairchild submitted seventeen exhibits in support of his application for post-conviction relief, approximately ten of which directly related to his claim of ineffective assistance of counsel. According to Mr. Fairchild, the medical records he submitted establish a history of drug (especially alcohol) use, head injuries, and amateur boxing that could have caused serious neurological damage. The OCCA did not dispute that the drug use, injuries, and boxing occurred. Rather, it concluded that the evidence presented was silent on the key question of whether trial counsel conducted a reasonably thorough investigation. According to the OCCA,

[Mr. Fairchild] claims trial counsel did not investigate [his] prior drug use, serious head injuries, and boxing activities. He presents no affidavit or statement from any witness, but only speculation, to support his claim that these matters were not investigated by trial counsel or direct appeal counsel. It is just as likely that the drug use, head injuries, and boxing activities were investigated by trial counsel and direct appeal counsel, and that trial counsel discussed them with Fairchild at the time of trial and rejected them as defense strategies.

Fairchild II, No. PC-98-31, slip op. at 8.

The OCCA also concluded that "none of [Mr. Fairchild's] Exhibits . . . support his suggestion that his drug use, head injuries, or boxing activities have had a lasting effect on his mental abilities." Id. at 9. The court noted that, although Mr. Fairchild submitted three articles explaining the long-term effects of professional boxing, those same articles concluded that there was little evidence of similar effects among amateur boxers (like Mr. Fairchild). The OCCA also cited Mr. Fairchild's psychiatric evaluation that depicts him as a normal, healthy individual. It is clear that the OCCA carefully considered the evidence presented by Mr. Fairchild before denying his claim of ineffective assistance of counsel on the merits. At least arguably, on the basis of this evidence, the OCCA did not unreasonably apply Strickland (nor otherwise commit error in light of AEDPA's deferential standards) in concluding that trial counsel's conduct was "consistent with reasonable trial strategy of competent counsel." Fairchild II, No. PC-98-31, slip op. at 8. However, we need not (and do not) definitively opine on this point. For present purposes, it is enough to note and underscore that the ineffectiveness claim in Mr. Fairchild's habeas petition is of a substantially different nature, based on evidence and arguments that were not previously considered by the OCCA, and that this claim is of sufficient weight that (if factually established) it might well support a conclusion of ineffective assistance under Strickland.

To be sure, not every new piece of evidence makes a claim a new one. See, e.g., Gardner v. Galetka, 568 F.3d 862, 881, 882 (10th Cir. 2009) (applying AEDPA deference to a state court determination on an ineffective assistance of counsel claim where new evidence submitted in federal court "would likely only have added color" to the claim presented in state court, and the difference between the new evidence and that presented in state court was "purely a matter of degree"). In Hawkins v. Mullin, 291 F.3d 658 (10th Cir. 2002), we noted that a habeas petitioner will be allowed to present "`bits of evidence'" to a federal court that were not presented to the state court that first considered his claim, without converting the claim into a new one. 291 F.3d at 670 (quoting Demarest v. Price, 130 F.3d 922, 932 (10th Cir. 1997)); Jones v. Hess, 681 F.2d 688, 694 (10th Cir. 1982) (quoting Nelson v. Moore, 470 F.2d 1192, 1197 (1st Cir. 1972)). But at a certain point, when new evidence so changes the legal landscape that the state court's prior analysis no longer addresses the substance of the petitioner's claim, we must necessarily say that the new evidence effectively makes a new claim — one that the state court has not adjudicated on the merits.

"A claim is more than a mere theory on which a court could grant relief; a claim must have a factual basis, and an adjudication of that claim requires an evaluation of that factual basis." Wilson II, 577 F.3d at 1291, 2009 WL 2623336, at *6. Mr. Fairchild only briefly mentioned the possibility of brain damage in his state application. His argument was general and unfocused. It centered upon trial counsel's alleged failure to properly investigate mitigating evidence, as reflected by the fact that counsel did not present any evidence of his history of drug use, fighting, and amateur boxing. The important link between these particular events and the possibility that Mr. Fairchild had physical, organic brain injury was far from salient in Mr. Fairchild's evidentiary showing. Moreover, even if the evidence presented suggested that Mr. Fairchild could have suffered physical brain damage, he presented only minimal evidence to suggest that he had, in fact, suffered such a permanent impairment. That is, he presented only minimal evidence that if trial counsel had actually undertaken a proper investigation of such an impairment that he would have found the impairment to be present. See Romero v. Tansy, 46 F.3d 1024, 1030 (10th Cir. 1995) (noting that a court "must consider the potential value to the defense of the evidence that might have been discovered in assessing the reasonableness of counsel's failure to conduct further investigation").

On the other hand, the two affidavits that Mr. Fairchild submitted with his federal habeas petition (i.e., affidavits of Drs. Smith and Crown) squarely addressed these evidentiary deficiencies — establishing the link between his prior history of drug abuse and head injuries and possible physical, organic brain injury; and furnishing evidence that he in fact had such an injury. A month before trial, Dr. Smith conducted a three-hour psychiatric interview with Mr. Fairchild. Dr. Smith states that he was instructed prior to his psychiatric interview to focus on the effects of alcohol. See R., Vol. I, Doc. 15, App. J ¶ 3 (Aff. of Dr. John Smith, dated May 2, 2002) (noting that the purpose of the evaluation, as he understood it, was to determine "the effect, if any, of drugs and alcohol on Mr. Fairchild on the night he was accused of killing Adam Broomhall"). Dr. Smith prepared a written report, however, that noted, among other findings, that Mr. Fairchild "suffered from a severe organic brain syndrome of an acute and chronic nature." Id. ¶¶ 8-9. This supports Mr. Fairchild's contention that trial counsel prematurely decided to focus only on alcohol abuse before considering the availability of other more powerful mitigating evidence.

Significantly, it appears that trial counsel spent very little time with Dr. Smith discussing the results of his examination. According to Dr. Smith, his primary contact with trial counsel after examining Mr. Fairchild was "a brief conversation during a recess of Mr. Fairchild's court proceedings, just before I testified" which involved "little or no discussion of my findings." Id. ¶ 10. Dr. Smith "saw no indication [trial counsel] made a decision not to discuss Mr. Fairchild's organic brain damage or his history of head injuries." Id. ¶ 12. Instead, Dr. Smith stated, counsel "never really asked me about it . . . and I simply did not have the opportunity to explore it with him." Id. This plausibly suggests that no reasoned decision was made not to present such evidence at trial, or if a decision was made, it was made before counsel possessed sufficient knowledge to weigh the potential importance of the evidence. While Dr. Smith's opinion that counsel's approach was "most unusual" — giving rise to fear that the "case was being thrown together rather than fully explored," id. — is of limited value, the facts averred in the affidavit support our similar concerns.

Dr. Crown reviewed Mr. Fairchild's medical records and conducted a battery of neuropsychological tests in April of 2002. See R., Vol. I, Doc. 15, App. I (Aff. of Dr. Barry Crown, dated Apr. 24, 2002). Dr. Crown notes that Mr. Fairchild's history "reflected several markers or signs indicating the possibility of organic brain damage." Id. ¶ 3. Dr. Crown identified numerous specific incidents that could have caused "actual physical damage to or malformation of the brain," including "cysts, tumors, . . . voids," or "tearing . . . of neural tissues as well as metabolic irregularities." Id. Such injuries could have been caused by (1) organized boxing from 14 to 17 years of age, (2) regular bar fights instigated by his boxing trainer, (3) a 15-30 second period of unconsciousness accompanied by jerking movements after being struck in the face by a large Marine which caused his head to strike a pole, (4) hospitalization in 1989 after being struck twice on the head by a two-by-four when Mr. Fairchild attempted to stop a thief from stealing tools, (5) a 1992 incident where, after being pushed down on blacktop, Mr. Fairchild was unable to walk and was numb from the waist down for a period of time, and for which radiological testing indicated a possible fracture to the left zygomatic arch (located between the cheekbone and the ear), or (6) an assault in 1992 in which Mr. Fairchild was struck in the back of the head, causing a nasal fracture and dental injuries. Id. ¶¶ 4-5.

The tests administered by Dr. Crown led him to conclude that "[t]here are multiple functional deficits reflecting damage primarily associated with the frontotemporal portions of the brain." Id. ¶ 10. He found that Mr. Fairchild's "[r]easoning, judgment, and problem solving are significantly impaired." Id. ¶ 11. "Mr. Fairchild exhibits also an auditory attention deficit of organic origin. Mr. Fairchild may not perceive stimuli in the same way fully functioning individuals would and may completely misinterpret what he sees and hears." Id. ¶ 13. The affidavits of Drs. Smith and Crown, taken together, suggest more than alcohol-induced explosiveness (i.e., that Mr. Fairchild was a mean drunk) — they point to the possibility of separate physical brain damage, which could be aggravated in a pathologically severe way by the ingestion of alcohol. See R., Vol. I, Doc. 15, at 72 ("Alcohol affects Mr. Fairchild differently from people without brain damage. Alcohol acts as a trigger to Mr. Fairchild's underlying brain damage.").

We find that this evidence "significantly altered [his] ineffective assistance of counsel claim, placing it in a much stronger legal posture than in the state court proceedings." Demarest, 130 F.3d at 933. If borne out upon investigation by trial counsel, as Dr. Crown's later affidavit suggests that it would have been, such evidence could have provided an important explanation for the jury, similar to what we described in Smith v. Mullin: that although the jury had received evidence of the defendant's impulsiveness and lack of control, what was lacking was "an explanation of how [the defendant's] organic brain damage caused these outbursts of violence and caused this `kind hearted' person to commit such a shocking crime." 379 F.3d at 943. Although trial counsel did provide an explanation of sorts through his emphasis on the effect of alcohol on Mr. Fairchild (whereas Mr. Smith's counsel was not even aware that mental health issues could be presented in mitigation, see id. at 939), if that explanation was selected before a reasonable investigation was conducted or no reasonable decision not to investigate further was made, the decision would violate Strickland, Terry Williams, and Wiggins v. Smith, 539 U.S. 510, 123 S.Ct. 2527, 156 L.Ed.2d 471 (2003). See, e.g., Terry Williams, 529 U.S. at 396, 120 S.Ct. 1495 (finding that the failure to introduce the "voluminous amount" of potentially mitigating evidence "clearly demonstrate[s] that trial counsel did not fulfill their obligation to conduct a thorough investigation").

Indeed, we conclude that, if established, the facts reflected in the additional evidence that Mr. Fairchild has presented in his habeas proceeding might well support a claim of ineffective assistance under Strickland. However, at this juncture we decline to decide whether trial counsel's performance was unconstitutionally deficient. Before we can pass on the merits of Mr. Fairchild's ineffective assistance claim, he must first exhaust all available state-court remedies. 28 U.S.C. § 2254(b)(1)(A); Bland v. Sirmons, 459 F.3d 999, 1011 (10th Cir. 2006). Exhaustion requires that the claim be "fairly presented" to the state court, which "means that the petitioner has raised the `substance' of the federal claim in state court." Bland, 459 F.3d at 1011; McCormick v. Kline, 572 F.3d 841, 851 (10th Cir. 2009) ("Exhaustion is a doctrine of comity and federalism `dictat[ing] that state courts must have the first opportunity to decide a [habeas] petitioner's claims.'") (alterations in original) (quoting Rhines v. Weber, 544 U.S. 269, 273, 125 S.Ct. 1528, 161 L.Ed.2d 440 (2005)).

Our decision in Demarest is strikingly similar to this one. There, the petitioner presented an ineffective assistance of counsel claim to the state court pursuant to post-conviction relief procedures, and the court denied the claim on the merits. Demarest, 130 F.3d at 929. In federal court, the petitioner produced powerful new evidence showing that trial counsel had failed to conduct a reasonable investigation of mitigating evidence. Id. at 933. The federal district court granted the petitioner's motion for a writ of habeas corpus, but this court reversed in a thorough and scholarly opinion by our current Chief Judge (Henry). The court emphatically agreed with the district court's "incisive analysis of the conduct of [petitioner's] trial counsel," based on the new evidence, and found that conduct "objectively unreasonable and materially prejudicial." Id. at 943. However, that assessment could "only be reached by considering important evidence not presented to the state courts in the post-conviction proceedings." Id.; see id. at 938-39. Accordingly, the court held that "our respect for the state courts requires us to remand this case to the district court for a determination of whether this new evidence could now be presented in those courts." Id. at 943. If so, "then it is those courts, rather than the federal court, that should have the opportunity to initially consider it." Id. We conclude that a similar approach is called for here.

As in Demarest, Mr. Fairchild has "transformed his claim from one involving only general allegations of failing to investigate . . . and only a minimal showing of prejudice into one involving a concrete reference to a qualified expert who could have been produced at trial" to present significant scientific evidence regarding Mr. Fairchild's mental condition. See id. at 938. The OCCA was never presented with the specific allegations contained in Mr. Fairchild's federal habeas petition. Nor was it provided with the affidavits of Drs. Smith and Crown. Because Mr. Fairchild has not fairly presented this claim to the OCCA, he has not satisfied the exhaustion requirement.

When a petitioner raises a new claim in federal court that is not barred on other procedural grounds, the federal court may, in appropriate circumstance, hold the federal case in abeyance to allow the petitioner to take his unexhausted claim back to state court for adjudication. Rhines, 544 U.S. at 278-79, 125 S.Ct. 1528; see Clements v. Maloney 485 F.3d 158, 169 n. 16 (1st Cir. 2007) ("The `stay and abeyance' procedure is a response to AEDPA's one-year statute of limitations and total exhaustion requirement; it was endorsed by a number of circuit courts, including ours, prior to the Supreme Court's decision in Rhines."); Poindexter v. Mitchell, 454 F.3d 564, 570 n. 2 (6th Cir. 2006) ("Post-AEDPA, courts now have discretion to stay a mixed habeas petition to allow a petitioner to present his unexhausted claims to the state court, and then return to federal court."); see also Anne R. Traum, Last Best Chance for the Great Writ: Equitable Tolling and Federal Habeas, 68 Md. L. Rev. 545, 588 (2009) (discussing the stay-and-abeyance procedure and noting that Rhines "makes clear that the AEDPA did not strip the courts of their traditional equitable discretion to manage their docket and ensure access to federal habeas review"); cf. Gardner, 568 F.3d at 869 (noting that "the district court allowed [petitioner] to amend his petition, but held the added claim in abeyance until he had exhausted state avenues for relief on the claim"); Anderson v. Sirmons, 476 F.3d 1131, 1135 (10th Cir. 2007) (noting district court's determination to deny petitioner's "request to decide the unexhausted ineffective assistance claim on the merits and, instead, abated [petitioner's] habeas petition so he could return to state court and exhaust the claim").

In Rhines, the Court discussed the circumstances under which the district court should employ the stay-and-abeyance procedure:

Because granting a stay effectively excuses a petitioner's failure to present his claims first to the state courts, stay and abeyance is only appropriate when the district court determines there was good cause for the petitioner's failure to exhaust his claims first in state court. Moreover, even if a petitioner had good cause for that failure, the district court would abuse its discretion if it were to grant him a stay when his unexhausted claims are plainly meritless.

. . . .

. . . [I]t likely would be an abuse of discretion for a district court to deny a stay and to dismiss a mixed petition if the petitioner had good cause for his failure to exhaust, his unexhausted claims are potentially meritorious, and there is no indication that the petitioner engaged in intentionally dilatory litigation tactics. In such circumstances, the district court should stay, rather than dismiss, the mixed petition.

Rhines, 544 U.S. at 277-78, 125 S.Ct. 1528; see also Clements, 485 F.3d at 169 (noting that "[i]n Rhines, the Court identified the three prerequisites for the `stay and abeyance' procedure," i.e., good cause for failure to exhaust, a potentially meritorious unexhausted claim, and lack of indication that petitioner intentionally participated in dilatory litigation tactics). If the state court resolves the unexhausted claim on the merits, AEDPA deference applies. See supra Part II.A. If the state court resolves the unexhausted claim on a procedural ground, such as a procedural bar under state law, the federal court will review that disposition, applying the standard of review that is appropriate under the circumstances. See Gardner, 568 F.3d at 870.

Although we decline to definitively decide the merits of Mr. Fairchild's unexhausted ineffective assistance claim, we have no doubt that this claim is "potentially meritorious" within the contemplation of Rhines. See Miller v. Dretke, 431 F.3d 241, 256 (5th Cir. 2005) (Garza, J., dissenting) ("Based on the above, I find the materiality question to be close. At the very least, Miller's Brady claim is not plainly meritless. For that reason, I would remand to the district court with instructions to determine if the first and third prongs of Rhines v. Weber are satisfied and to stay and abey the proceedings if they are."); see also Whitley v. Ercole, 509 F.Supp.2d 410, 420 (S.D.N.Y. 2007) (applying the Rhines criteria, and noting that, "[h]aving reviewed the record and Petitioner's submissions, I conclude that Petitioner has shown that his unexhausted claim alleging ineffective assistance of counsel has potential merit"); cf. Haynes v. Quarterman, 526 F.3d 189, 196-97 (5th Cir. 2008) (holding the petitioner's unexhausted claims of ineffective assistance relating to the presentation of mitigating evidence had "no potential merit" where petitioner "alleges that mitigating evidence could have influenced the jury's discretion but does not argue that evidence not presented due to alleged ineffective assistance of counsel would render him ineligible for the death penalty"). Accordingly, we believe that Mr. Fairchild should have an opportunity to establish that the use of the stay-and-abeyance procedure concerning his potentially meritorious ineffective assistance claim would otherwise be appropriate on these facts. See, e.g., Akins v. Kenney, 410 F.3d 451, 456 (8th Cir. 2005) ("We remand to permit the district court to exercise its discretion on this matter in the first instance within the framework set forth in Rhines v. Weber."); see also Dolis v. Chambers, 454 F.3d 721, 725 (7th Cir. 2006) ("In keeping with Rhines, the district court would naturally have discretion to decide whether a stay was warranted in the particular circumstances of each case.").

In particular, Mr. Fairchild should be permitted to demonstrate that he had good cause for failing to exhaust the claim. See King v. Ryan, 564 F.3d 1133, 1136 (9th Cir. 2009) (noting that "importantly, [the Rhines stay-and-abeyance procedure] is available only upon a showing that the petitioner had good cause for not exhausting his state claims earlier"), petition for cert. filed, ___ U.S.L.W. ___ (U.S. July 2, 2009) (No. 09-5100); cf. Clements, 485 F.3d at 171 ("Clements' lack of good cause means that, under Rhines, he cannot take advantage of the `stay and abeyance' procedure. Therefore, we affirm the denial of a stay."); see also Pace v. DiGuglielmo, 544 U.S. 408, 416, 125 S.Ct. 1807, 161 L.Ed.2d 669 (2005) ("A petitioner's reasonable confusion about whether a state filing would be timely will ordinarily constitute `good cause' for him to file in federal court." (citing Rhines, 544 U.S. at 278, 125 S.Ct. 1528)). In this connection, we acknowledge that the good cause requirement should not be "the sort of strict and inflexible requirement that would trap the unwary pro se prisoner." Rhines, 544 U.S. at 279, 125 S.Ct. 1528 (Stevens, J., concurring) (internal quotation marks omitted) (quoting Rose v. Lundy, 455 U.S. 509, 520, 102 S.Ct. 1198, 71 L.Ed.2d 379 (1982)); see Ellison v. Rogers, 484 F.3d 658, 662 (3d Cir. 2007) (noting that "[w]e are mindful of Justice Stevens' concurrence" concerning the good cause requirement not being a trap for the unwary pro se litigant, but noting that the prisoner before the court "is not an unwary petitioner").

Furthermore, "if a petitioner presents a district court with a mixed petition and the court determines that stay and abeyance is inappropriate, the court should allow the petitioner to delete the unexhausted claims and to proceed with the exhausted claims if dismissal of the entire petition would unreasonably impair the petitioner's right to obtain federal relief." Rhines, 544 U.S. at 278, 125 S.Ct. 1528; see Allen, 568 F.3d at 1201 n. 7. The district court should consider the propriety of granting Mr. Fairchild this option, if it ultimately decides not to employ the stay-and-abeyance procedure.

We are aware that the Second Circuit has handled differently the situation of additional evidence presented for the first time in a habeas petition. In Wilson v. Mazzuca, 570 F.3d 490 (2d Cir. 2009) (Cabranes, J.), that court held that where the state court adjudicates a habeas claim on the merits, but the factual record properly before the federal court includes additional evidence, the federal court may take that new evidence into consideration in determining whether the state court decision was unreasonable. 570 F.3d at 500. "Where, as here, the habeas claim is brought under 28 U.S.C. § 2254(d)(1), a habeas court asks whether there was `an unreasonable application of clearly established Federal law,' in light of all the facts and circumstances — including whatever facts are discovered during a post-conviction hearing in federal court subject to the requirements of 28 U.S.C. § 2254(e)(1)." Id. According to that court, "[a]ny new evidence uncovered in the federal proceeding is relevant only insofar as it assists the habeas court in determining whether the state court reached an unreasonable application of law." Id.

With all respect, that is not a logical reading of AEDPA. AEDPA explicitly provides that federal court review of the reasonableness of the state court's factual findings must be made "in light of the evidence presented in the State court proceeding." 28 U.S.C. § 2254(d); see Hammon v. Ward, 466 F.3d 919, 928 (10th Cir. 2006) ("In reviewing the OCCA's adjudication of Petitioner's ineffective assistance of appellate counsel claim, we consider the record as it existed before the OCCA."). Evidence presented for the first time in federal court is not relevant to whether the state court decision was "contrary to, or involved an unreasonable application of, clearly established Federal law." 28 U.S.C. § 2254(d)(1). It is surely not "unreasonable" for the state court to base its decision on the only facts that have been put before it. On the other hand, if the new evidence is of such a character that the federal court is presented with a substantially different issue, not decided by the state court, then no deference is due. New evidence may produce a "new claim," but it cannot render the state court's determination of the same claim unreasonable.

In sum, we conclude that Mr. Fairchild has presented a potentially meritorious claim of ineffective assistance of counsel. However, he did not exhaust that claim before the state courts. Specifically, the claim is predicated on new powerful evidence that Mr. Fairchild never presented to the OCCA. That evidence has effectively transformed the ineffective assistance claim that Mr. Fairchild presented to the OCCA into a new claim. But before we will pass on the merits of that claim, principles of comity and efficient judicial administration, oblige us to insist that Mr. Fairchild exhaust his claim. And we have concluded that the district court should determine under the circumstances of this case the appropriateness of using the stay-and-abeyance procedure to permit Mr. Fairchild to pursue exhaustion.

C. Other Claims and Total Exhaustion

In addition to his unexhausted ineffective assistance claim, Mr. Fairchild has brought several other claims that are exhausted. He argues that (1) the jury instructions failed to adequately explain the possible sentence of life without possibility of parole; (2) application of Oklahoma court decisions regarding the applicable mens rea for child abuse murder violates the Fourteenth Amendment; (3) Oklahoma's mens rea requirement for child abuse murder violates the Eighth Amendment; and (4) the exclusion of lesser-included or lesser-related offense instructions violated federal rights. We must decline to address on the merits these arguments because of the total exhaustion doctrine.

"Congress has emphatically directed us that habeas petitioners seeking relief in federal court must first exhaust all available state court remedies — that is, unless doing so would be futile because of `an absence of available State corrective process' or because `circumstances exist that render such process ineffective to protect the rights of the applicant.'" Magar v. Parker, 490 F.3d 816, 818 (10th Cir. 2007) (quoting 28 U.S.C. § 2254(b)(1)). Under this requirement, "federal district courts may not adjudicate mixed petitions for habeas corpus, that is, petitions containing both exhausted and unexhausted claims." Rhines, 544 U.S. at 273, 125 S.Ct. 1528 (summarizing Rose, 455 U.S. at 518-19, 102 S.Ct. 1198); see also Allen, 568 F.3d at 1201 n. 7 (discussing mixed petitions and Rhines).

When a district court is presented with a petition containing both exhausted and unexhausted claims and addresses all of the claims on the merits, the proper approach on appeal ordinarily is to

vacate[] the order . . . and remand[] the case to the district court so that it [can] do one of four things: (1) dismiss the mixed petition in its entirety, Rhines, 544 U.S. at 274, 125 S.Ct. 1528; (2) stay the petition and hold it in abeyance while the petitioner returns to state court to raise his unexhausted claims, id. at 275, 125 S.Ct. 1528; (3) permit the petitioner to dismiss the unexhausted claims and proceed with the exhausted claims, id. at 278, 125 S.Ct. 1528; or (4) ignore the exhaustion requirement altogether and deny the petition on the merits if none of the petitioner's claims has any merit, 28 U.S.C. § 2254(b)(2).

Harris v. Lafler, 553 F.3d 1028, 1031 (6th Cir. 2009) (emphasis omitted); see, e.g., Cassett v. Stewart, 406 F.3d 614, 625 (9th Cir. 2005) (instructing the district court on remand "to consider, consistent with Rhines, whether to stay the proceedings, hold in abeyance [the] exhausted petition, and dismiss without prejudice his unexhausted . . . claim so that he can present it to the . . . state courts"). Under the unique circumstances of this case, we have determined that in the first instance upon remand the district court should examine the second option noted above — viz., it should give Mr. Fairchild the opportunity to establish that the use of the stay-and-abeyance procedure concerning his potentially meritorious ineffective assistance claim would be appropriate on these facts.

The inefficiencies of this course of action are not lost on us. The district court addressed Mr. Fairchild's exhausted claims on the merits and the parties have fully briefed them on appeal. Moreover, if the district court determines that use of the stay-and-abeyance procedure is not warranted in this case, then the court may simply allow Mr. Fairchild to "dismiss and abandon [his] unexhausted claim and then reenter the very judgment that is now before us." Rockwell v. Yukins, 217 F.3d 421, 425 (6th Cir. 2000).

Nevertheless, it is AEDPA that requires us to remand without addressing these claims on the merits. See id. ("It is AEDPA, however, that mandates our decision, not the whims of this panel."). Moreover, the Court has made it abundantly clear that "before you bring any claims to federal court, be sure that you first have taken each one to state court." Rose, 455 U.S. at 520, 102 S.Ct. 1198. While the decision to remand without addressing the exhausted claims on the merits is "admittedly inefficient in the present case," we believe that this approach will "promote overall judicial efficiency and other important values." Rockwell, 217 F.3d at 425; see Rose, 455 U.S. at 518-19, 102 S.Ct. 1198 (requiring the dismissal of mixed petitions in order to preserve comity and reduce the temptation of district courts to consider unexhausted claims).

III. CONCLUSION

For the foregoing reasons, we VACATE the district court's judgment and REMAND for the district court to determine whether to use the stay-and-abeyance procedure to permit Mr. Fairchild to exhaust his new potentially meritorious claim for ineffective assistance of counsel and for it to conduct further proceedings consistent with this opinion. We do not reach the merits of Mr. Fairchild's other claims of error.