OPINION
SPROUSE, Senior Circuit Judge:Kermit Smith, Jr. is a North Carolina prisoner who was sentenced to death following his conviction of the December 3, 1980 first-degree murder, second-degree rape, and common-law robbery of Whelette Collins. The district court granted Smith’s habeas corpus petition,1 finding that an instruction given to the jury that sentenced Smith to death was unconstitutionally vague, and required that Smith receive a new sentencing hearing. Smith v. Dixon, 766 F.Supp. 1370 (E.D.N.C.1991). The State of North Carolina, through the warden of the prison where Smith is incarcerated, appeals this decision. Smith cross-appeals, arguing that the district court erred in failing to find that the additional grounds he advanced provided a basis for relief. We affirm.
I. BACKGROUND
The gruesome facts surrounding Collins’s long ordeal and subsequent murder are described in the opinion of the district court, id. at 1373-74, and the decision of the Supreme Court of North Carolina affirming Smith’s conviction and sentence on direct appeal, State v. Smith, 305 N.C. 691, 292 S.E.2d 264, cert. denied, 459 U.S. 1056, 103 S.Ct. 474, 74 L.Ed.2d 622 (1982). Briefly, Smith kidnapped Collins and her two companions at gunpoint and took them to deserted woods. The psychological and physical torture Collins experienced lasted for many hours before she was murdered. While her two friends were locked in the trunk of a car, Smith threatened Collins with death and brutally raped her. Following the rape, Smith forced her to remain naked outside at night in below freezing December temperatures for a substantial period of time, mocking her as she begged him for clothing or a blanket. Smith then bludgeoned Collins with a cinder block and dragged her body to a quarry pond where he crammed her feet inside the cinder block to make her body sink. The blunt trauma to Collins’s head fractured her skull; she died from this injury. Her companions escaped from the trunk of the car physically unharmed.
After the jury convicted Smith, the trial court held a sentencing hearing in which it submitted four aggravating circumstances and five mitigating circumstances for the jury’s consideration. Regarding one of the aggravating circumstances, whether the murder was “especially heinous, atrocious or cruel,” the court instructed:
*670[E]very murder is not especially heinous, it is not atrocious nor cruel. While every murder, if it results from an unlawful killing, of course, is a violation of the law, but it does not necessarily mean that there is anything aggravated about it or that it was especially heinous or atrocious or cruel. And our Supreme Court has said that the words “especially heinous, atrocious or cruel” means extremely or especially or particularly heinous or atrocious or cruel. Heinous means extremely wicked or shockingly evil. Atrocious means marked by or given to extreme wickedness, brutality or cruelty, marked by extreme violence or savagely fierce. It means outrageously wicked and violent. Cruel means designed to inflict a high degree of pain, utterly indifferent to or the enjoyment of suffering of others.
The jury found the existence of all four of the aggravating circumstances submitted by the judge: that Smith committed the murder while (1) raping, (2) robbing, and (3) kidnapping Collins, and (4) that the murder was “especially heinous, atrocious or cruel.” The jury found the existence of one of the five mitigating circumstances: that Smith committed the murder while under the influence of a mental or emotional disturbance. The jury determined that the aggravating circumstances outweighed the mitigating circumstances, and recommended that Smith be sentenced to death.
A. Direct Appeal
Smith appealed his conviction and sentence, but did not challenge the constitutionality of the heinousness factor. The Supreme Court of North Carolina conducted a review of the record pursuant to N.C.Gen. Stat. § 15A-2000(d), determined that the evidence was sufficient to support each of the aggravating factors, and affirmed Smith’s conviction and sentence. Smith, 292 S.E.2d at 276-77. The United States Supreme Court denied Smith’s request for certiorari, and Smith’s conviction became final on November 29, 1982. Smith v. North Carolina, 459 U.S. 1056, 103 S.Ct. 474, 74 L.Ed.2d 622 (1982).
B. Motion for Appropriate Relief
Smith filed his first application for post-conviction relief in North Carolina superior court in June of 1983. See N.C.Gen.Stat. § 15A-1415. Smith’s Motion for Appropriate Relief raised 57 grounds attacking his conviction and sentence, which were grouped into five “claims.” In Claim IV Smith raised for the first time the argument that the § 15A-2000(e)(9) statutory aggravating factor of heinousness was unconstitutionally vague in violation of the Eighth and Fourteenth Amendments, and that the jury was not charged with a constitutionally limiting definition of this factor. In addition, in 13 of the 14 issues he raised in Claim V, Smith maintained that he was denied his Sixth Amendment right to effective assistance of counsel at trial. Smith alleged in his Motion for Appropriate Relief two errors at the direct appeal stage: under Claim IV he argued that North Carolina’s system of appellate review of death sentences was constitutionally inadequate, and under Claim V he argued that he had been denied the right to effective assistance of appellate counsel because his attorney had failed to advance on direct appeal many of the issues raised in his Motion for Appropriate Relief. Before the State responded to Smith’s motion, the superior court entered an order summarily denying all of Smith’s claims, except those based on ineffective assistance (Claim V). State v. Smith, Nos. 80 CRS 15265, 15266, 15271 (N.C.Super.Ct. Aug. 19, 1983).2
Following an evidentiary hearing on the allegations of ineffective assistance, the supe*671rior court denied the remaining claims in Smith’s Motion for Appropriate Relief. State v. Smith, Nos. 80 CRS 15265, 15266, 15271 (N.C.Super.Ct. Dec. 16, 1983). The Supreme Court of North Carolina summarily denied Smith’s petition for a writ of certiorari, State v. Smith, 333 S.E.2d 495 (N.C.1985), as did the United States Supreme Court, Smith v. North Carolina, 474 U.S. 1026, 106 S.Ct. 582, 88 L.Ed.2d 565 (1985).3
C. District Court’s Opinion
In May 1988, Smith filed his habeas corpus petition in the federal District Court for the Eastern District of North Carolina, seeking relief under 28 U.S.C. § 2254. The district court, in an opinion rendered before the Supreme Court’s decision in Coleman v. Thompson, — U.S.-, 111 S.Ct. 2546, 115 L.Ed.2d 640 (1991), concluded that consideration by a federal court of Smith’s claims was not barred by procedural default because the last state court opinion addressing these claims had not included a plain statement that it based the decision on state grounds. Smith v. Dixon, 766 F.Supp. 1370, 1376 (E.D.N.C.1991). Turning to the merits, the district court found that the heinousness instruction was unconstitutionally vague under Maynard v. Cartwright, 486 U.S. 356, 108 S.Ct. 1853, 100 L.Ed.2d 372 (1988), and that Smith was not foreclosed by Teague v. Lane, 489 U.S. 288, 109 S.Ct. 1060, 103 L.Ed.2d 334 (1989), from raising this as error. Smith, 766 F.Supp. at 1379-86. It further held that the Supreme Court of North Carolina did not cure the vagueness error by reweighing the evidence or conducting a constitutional harmless-error analysis. Id. at 1386. The district court declined the State’s invitation to conduct harmless-error analysis in the first instance, id., and rejected the numerous other errors asserted by Smith, id. at 1386-96. The court conditionally granted habeas relief, ordering that Smith’s death sentence be set aside unless the State retried him within 180 days. Smith v. Dixon, No. 88-337 (E.D.N.C. Aug. 14,1991). In addition, the district court stayed entry of judgment to permit the State to petition the Supreme Court of North Carolina for “further review ... in accordance with Clemons v. Mississippi.” Id. (citing Clemons, 494 U.S. 738, 110 S.Ct. 1441, 108 L.Ed.2d 725 (1990)).
In October 1991, the State petitioned the Supreme Court of North Carolina to clarify the basis for the decision it rendered in Smith’s direct appeal. The Supreme Court of North Carolina denied the request, believing that it lacked jurisdiction to hear the matter. State v. Smith, 330 N.C. 617, 412 S.E.2d 68 (1991). Accordingly, the district court ordered its prior decision into effect. Smith v. Dixon, No. 88-337 (E.D.N.C. Dec. 2, 1991). Both the State and Smith appeal.
II. REVIEWABILITY OF FEDERAL CLAIMS4
Before reaching the merits of Smith’s claims, we must determine whether it is appropriate to do so. Federal habeas courts generally “will not review a question of federal law decided by a state court if the decision of that court rests on a state law ground that is independent of the federal question and adequate to support the judgment.” Coleman v. Thompson, — U.S. -, -, 111 S.Ct. 2546, 2553-54, 115 L.Ed.2d 640 (1991). This doctrine bars federal courts from addressing federal claims raised under § 2254 when a state court has declined to grant relief on them because the petitioner failed to meet a state procedural requirement. Id. at-, 111 S.Ct. at 2557. The first issue this court must decide, then, *672is whether Smith has procedurally defaulted on his federal claims.
As the Supreme Court has stated, determining whether a state decision denying federal claims rests on federal or state law is not always easy because often state-court opinions are unclear concerning the basis for their rulings. See id. at-, 111 S.Ct. at 2555. To assist federal courts in determining when application of the independent and adequate state grounds doctrine bars federal proceedings, the Court has provided the following direction:
“[Wjhen ... a state court decision fairly appears to rest primarily on federal law, or to be interwoven with the federal law, 'and when the adequacy and interdependence of any possible state law ground is not clear from the face of the opinion, [federal courts] will accept as the most reasonable explanation that the state court decided the case the way it did because it believed that federal law required it to do so.”
Id. at-, 111 S.Ct. at 2556 (quoting Michigan v. Long, 463 U.S. 1032, 1040-41, 103 S.Ct. 3469, 3476, 77 L.Ed.2d 1201 (1983)).
Therefore, when a federal court receives a habeas petition presenting federal claims, it may address those claims only “if the decision of the last state court to which the petitioner presented his federal claims fairly appeared to rest primarily on resolution of those claims, or to be interwoven with those claims, and did not clearly and expressly rely on an independent and adequate state ground.” Id. -U.S. at-, 111 S.Ct. at 2557.
Under North Carolina law, a Motion for Appropriate Relief may be denied when “[u]pon a previous appeal the defendant was in a position to adequately raise the ground or issue underlying the present motion but did not do so.” N.C.Gen.Stat. § 15A-1419(a)(3). Because Smith could have challenged the constitutionality of the heinousness factor in his direct appeal to the North Carolina Supreme Court, the superior court properly could have found that presentation of this claim in a later Motion for Appropriate Relief was procedurally barred.5 It is not, however, enough that the superior court could have relied on procedural bar, for it actually must have based its decision on procedural default in order to prevent federal habeas review. See Caldwell v. Mississippi 472 U.S. 320, 327, 105 S.Ct. 2633, 2638, 86 L.Ed.2d 231 (1985).6
In its order denying Smith’s Motion for Appropriate Relief, the superior court did not include a plain statement either that its decision rested on procedural bar or that it rested on the merits. It stated merely: “The court has read the paperwriting and considered the arguments in support of the claims set out therein. The court finds as a fact that Claims No. I, II, III, and IV [including the vagueness challenge], set forth no probable grounds for relief.” We think the circumstances in Smith’s case are similar to the ones we considered in Nickerson v. Lee, 971 F.2d 1125 (4th Cir.1992), cert. denied, U.S. -, 113 S.Ct. 1289, 122 L.Ed.2d 681 (1993).
In Nickerson a panel of this court also reviewed a vague North Carolina superior *673court order denying a defendant’s Motion for Appropriate Relief under N.C.Gen.Stat. § 15A-1419. The panel determined that the state court had denied the defendant’s federal claims for substantive, not procedural, reasons. Nickerson, 971 F.2d at 1128-30. The superior court order reviewed by the Nicker-son panel stated that “upon review of the motion and the file in the case [the court] finds that the petitioner has set forth no grounds for which he is entitled to a motion for appropriate relief.” Id. at 1128. The Nickerson court held that this language showed that the superior court had denied the defendant’s claims on the merits, not because of procedural default. Id. at 1129. The language “implies that the [superior] court reached and reviewed the merits of each of Nickerson’s claims and concluded that he would not be entitled to relief on any of these claims.” Id.
In Coleman v. Thompson, — U.S.-, 111 S.Ct. 2546, 115 L.Ed.2d 640 (1991), the Supreme Court reached the opposite conclusion in a contrasting factual situation. It determined that a Virginia court’s order dismissing the defendant’s late notice of appeal was grounded on independent state law, even though the order lacked a plain statement of the reason for the dismissal. The Supreme Court found that, in light of the surrounding circumstances, the state court’s order “fairly appeared” to rest on procedural default. Id. at -, 111 S.Ct. at 2559-61. Those surrounding circumstances were that (1) the Commonwealth of Virginia had based its motion to dismiss entirely on procedural grounds (the late filing), and (2) the court’s order “dismissed” rather than “denied” the defendant’s notice of appeal. Id.; see Ylst v. Nunnemaker, — U.S.-,-, 111 S.Ct. 2590, 2594, 115 L.Ed.2d 706 (1991). The Court found that these-clues explained the state dismissal order, which, after reciting the papers submitted by the parties and their filing dates, stated only: “Upon consideration whereof, the motion to dismiss is granted and the petition for appeal is dismissed.” Coleman, — U.S. at -, 111 S.Ct. at 2553.
The Nickerson court distinguished Coleman, determining that a similar examination of the surrounding circumstances revealed no clues to the basis for the North Carolina superior court’s order. Unlike Coleman, where the State had responded to the defendant’s motion by arguing procedural bar, “[h]ere, it appears that North Carolina did not respond to Nickerson’s motion at all. Thus, unlike in Coleman, there is no basis for concluding ... that the state court’s judgment rested even in part on state law.” Nickerson, 971 F.2d at 1129. Smith’s ease, in that respect, is identical to Nickerson: North Carolina did not respond to Smith’s Motion for Appropriate Relief before the superior court denied Claims I-TV, which included the vagueness challenge.7
Like Nickerson and unlike Coleman, a review of other surrounding circumstances fails to disclose whether the superior court denied Smith’s vagueness claim on procedural grounds or on the merits. At least three factors point to the order’s inherent vagueness. First, although the court “denied” rather than “dismissed” Smith’s Motion for Appropriate Relief, the distinction does not provide the same guidance as it did in Coleman because North Carolina law, unlike Virginia law, provides that procedurally barred issues may be “denied” rather than “dismissed” when presented in a Motion for Appropriate Relief. N.C.Gen.Stat. § 15A-1419(a)(3). Second, the timing of the superi- or court’s order does not clarify whether the court denied Smith’s vagueness claim on procedural grounds or on the merits, because it issued the denial more than two months after Smith filed his motion.8 Finally, the superior court’s separation of Claims I-IV from Claim V does not illuminate the basis for its denial *674of the vagueness claim. The bottom line is that we cannot conclude that the superior court denied all the issues in Claims I-IV (including the vagueness challenge) for reasons of procedural default. The inclusive nature of the order’s language, like that in Nickerson, implies that the superior court considered the merits of the issues Smith raised in Claims I-IV. Certainly Smith’s challenge to the constitutional adequacy of North Carolina’s appellate review of death sentences, an issue he raised in Claim IV, was denied on the merits: it could not have been procedurally barred, because the first time that Smith could raise the issue was in his Motion for Appropriate Relief.9 Moreover, several of the issues Smith raised in Claims I-IV had been rejected on the merits by the North Carolina Supreme Court on direct appeal. Therefore, these issues were not procedurally barred; they were denied either under § 15A-1419(a)(2) because the superior court decided not to re-examine the merits,10 or because the superior court reexamined the merits and rejected them anew.
*675Because nothing in the surrounding circumstances indicates that the superior court denied any claims in Smith’s Motion for Appropriate Relief for reasons of procedural bar, and because we are bound by the holding of Nickerson, a case virtually indistinguishable from this one, we conclude that the district court correctly determined Smith was not procedurally barred from federal habeas review of his claims.
III. MERITS OF THE VAGUENESS CLAIM (STATE’S APPEAL)
Having held that the district court correctly ruled on the procedural-default issue, we review its rulings on the merits, beginning with its holding that the unconstitutional vagueness of the heinousness factor in Smith’s sentencing hearing was not cured by the North Carolina Supreme Court on direct appeal. In his habeas petition Smith attacked the North Carolina statutory aggravating factor for “especially heinous, atrocious, or cruel” murders, see N.C.Gen.Stat. § 15A-2000(e)(9), and the trial court’s instruction to the jury on this factor. Smith argued that the statutory definition and limiting instruction were unconstitutionally vague under Maynard v. Cartwright, 486 U.S. 356, 108 S.Ct. 1853, 100 L.Ed.2d 372 (1988). The district court agreed, and the State concedes as much on appeal.11 The State contends, however, relying on Clemons v. Mississippi, 494 U.S. 738, 110 S.Ct. 1441, 108 L.Ed.2d 725 (1990), that the North Carolina Supreme Court cured the error on direct appeal.
Because the district court found that the North Carolina Supreme Court did not cure the eiTor on direct appeal, it granted Smith a new sentencing hearing. We agree that the state supreme court did not remedy the vagueness error.
A. North Carolina Supreme Court Did Not Cure Vagueness Error
In Clemons the Supreme Court held that when sentencing instructions on the heinousness factor are found to have been unconstitutionally vague, a state appellate court in a “weighing” state — such as North Carolina — may remedy the error in one of three ways: (1) by finding the error harmless beyond a reasonable doubt, (2) by reweighing the aggravating and mitigating circumstances without the heinousness factor, or (3) by reweighing the aggravating and mitigating circumstances, using the correct definition of heinousness as constitutionally narrowed by the state court’s prior decisions. Id. at 751-52, 110 S.Ct. at 1449-50. The State contends that the vagueness error in Smith’s sentencing hearing was cured under the third method. It argues that in Smith’s 1982 direct appeal, the North Carolina Supreme Court, in reweighing the aggravating and mitigating circumstances in Smith’s case, applied the constitutionally narrowed definition that the North Carolina courts had developed at the time. That definition requires “evidence that the murder in question involved brutality in excess of that which is normally present in any killing.” State v. Martin, 303 N.C. 246, 278 S.E.2d 214, 220, cert. denied, 454 U.S. 933, 102 S.Ct. 431, 70 L.Ed.2d 240 (1981); State v. Goodman, 298 N.C. 1, 257 S.E.2d 569, 585 (1979). Excess brutality connotes a “conscienceless or pitiless crime which is unnecessarily torturous to the victim.” Goodman, 257 S.E.2d at 585; see State v. Silhan, 302 N.C. 228, 275 S.E.2d 450, 479 (1981).12
The district court rejected the State’s argument, finding it unclear whether the state supreme court, in reweighing the aggravating and mitigating circumstances, had applied North Carolina’s constitutionally narrowed definition of heinousness. Smith, 766 F.Supp. at 1385. We agree. The state supreme court’s ruling is not sufficiently clear for us to determine that it cured the vagueness error under Clemons. As the district court noted, the North Carolina Supreme Court did not cite Martin or Goodman or *676any other case applying North Carolina’s constitutionally narrowed definition. Moreover, “[t]hat the court found elements of brutality and torture in the murder does not necessarily mean that it was tacitly attempting to apply the Martin/Goodman standard.” Id. The North Carolina Supreme Court’s opinion is like the Mississippi Supreme Court’s opinion reviewed by the Supreme Court in Clemons. The Clemons Court found it unclear whether the Mississippi Supreme Court had applied its narrowed definition of heinousness (a murder that is conscienceless or pitiless and unnecessarily torturous to the victim), even though the latter’s opinion referred to “brutal and torturous facts.” Clemons, 494 U.S. at 751, 110 S.Ct. at 1449. Finally, in this context, we are unpersuaded by the State’s argument that the North Carolina Supreme Court clarified its opinion in Smith’s 1982 direct appeal by citing Smith in a 1983 opinion. See State v. Oliver, 309 N.C. 326, 307 S.E.2d 304, 317-19 (1983) (citing Martin, Goodman, and Smith). Because Oliver is a review of Oliver’s sentence, not Smith’s, it would be difficult to conclude that the Oliver court reweighed the aggravating and mitigating factors in Smith’s case. See Richmond v. Lewis, — U.S.-, -, 113 S.Ct. 528, 535-36, 121 L.Ed.2d 411 (1992).
B. Federal Habeas CouH May Not Examine Vagueness Error for Harmlessness in the First Instance
Although the North Carolina Supreme Court did not cure the vagueness error, the State urges us to find the error harmless. The district court believed that it lacked the authority to determine whether the vagueness error was harmless. Smith, 766 F.Supp. at 1386 & n. 7 (stating that if it had the authority, it “would not hesitate to hold that the underlying facts satisfy the Martin/Goodman standard”). The State contends that the district court did have the power to engage in harmless-error analysis, and it asks us to conduct the analysis in the first instance, given the district court’s dictum. We decline the invitation.
The Supreme Court has repeatedly referred to the power of state appellate courts to remedy a vagueness error such as the one here by conducting harmless-error analysis. See, e.g., Richmond v. Lewis, — U.S.-, -, 113 S.Ct. 528, 535, 121 L.Ed.2d 411 (1992) (“Where the death sentence has been infected by a vague or otherwise constitutionally invalid aggravating factor, the state appellate court or some other state sentencer must actually perform a new sentencing calculus.”); Sochor v. Florida, — U.S. -, ——, 112 S.Ct. 2114, 2123, 119 L.Ed.2d 326 (1992) (explaining how “state courts[’] ... review for harmless federal error will pass federal scrutiny”); Stringer v. Black, — U.S. -, -, 112 S.Ct. 1130, 1136, 117 L.Ed.2d 367 (1992) (“We require close appellate scrutiny of the import and effect of invalid aggravating factors to implement the well-established Eighth Amendment requirement of individualized sentencing determinations in death penalty cases.”); id. at-, 112 S.Ct. at 1140 (“[U]se of a vague or imprecise aggravating factor in the weighing process invalidates the sentence and at the very least requires constitutional harmless-error analysis or reweighing in the state judicial system.”); Clemons v. Mississippi, 494 U.S. 738, 754, 110 S.Ct. 1441, 1451, 108 L.Ed.2d 725 (1990) (holding that “state appellate courts ... [may] engage in reweighing or harmless-error analysis when errors have occurred in a capital sentencing proceeding”); see also Barclay v. Florida, 463 U.S. 939, 958, 103 S.Ct. 3418, 3429, 77 L.Ed.2d 1134 (1983) (referring to the Florida Supreme Court’s application of “its” harmless-error analysis); cf. Brecht v. Abraham-son, — U.S. -, -, 113 S.Ct. 1710, 1719, 123 L.Ed.2d 353 (1993) (distinguishing constitutional harmless-error analysis on direct review by a state supreme court from constitutional harmless-error analysis on federal habeas review).13 Significantly, even in *677cases decided on certiorari to federal habeas courts where the vague instruction, as here, violated the federal Constitution, cf. Barclay, 463 U.S. at 957-58, 103 S.Ct. at 3428-29 (vagueness error was a state-law violation), the Supreme Court has not remanded to the federal court for a determination whether the error was harmless, but has reiterated that it is up to the state appellate courts to remedy the error under one of the three Clemons methods, including harmless-error analysis. See, e.g., Stringer, — U.S. at-, 112 S.Ct. at 1140.
Like the two other Clemons methods of remedying vagueness errors, harmless-error analysis involves balancing: the reviewing court must decide whether the constitutional error affected the balance struck by the jury when it weighed aggravating circumstances against mitigating circumstances. Clemons, 494 U.S. at 754, 110 S.Ct. at 1451. This weighing of factual evidence, in our view, concerns a question of state law, “errors of which are not cognizable in federal habeas proceedings.” Lewis v. Jeffers, 497 U.S. 764, 783, 110 S.Ct. 3092, 3103, 111 L.Ed.2d 606 (1990). Therefore, the district court properly refrained from conducting harmless-error analysis in the first instance, as do we. Our holding is in accord with decisions of the two other circuits that have considered the issue. Jeffers v. Lewis, 974 F.2d 1075, 1084 & n. 11 (9th Cir.1992); Wiley v. Puckett, 969 F.2d 86, 94 n. 8 (5th Cir.1992).
IV. SMITH’S CROSS-APPEAL
A. The McKoy Claim
Turning to Smith’s cross-appeal, he raises only one issue which, in our view, merits detailed discussion — the issue involving the principle announced in McKoy v. North Carolina, 494 U.S. 433, 110 S.Ct. 1227, 108 L.Ed.2d 369 (1990). Smith alleged in his habeas petition that he was entitled to a new sentencing hearing because there was a reasonable likelihood that one or more jurors mistakenly believed they could, in weighing mitigating circumstances, consider only the evidence the jury had unanimously agreed was mitigating. McKoy holds that imposition of the death penalty under such circumstances violates the Eighth and Fourteenth Amendments of the Constitution. Id. at 444, 110 S.Ct. at 1234; see also Mills v. Maryland, 486 U.S. 367, 384, 108 S.Ct. 1860, 1870, 100 L.Ed.2d 384 (1988) (striking down Mary*678land’s unanimity requirement).14 Smith concedes that the sentencing verdict form in his case, unlike the one in McKoy, did not require unanimity for mitigating circumstances.15 He argues, however, that the court’s sentencing instructions were so misleading as to result in McKoy error.
He analogizes his case to State v. McNeil, 327 N.C. 388, 395 S.E.2d 106 (1990), cert. denied, — U.S. -, 111 S.Ct. 1403, 113 L.Ed.2d 459 (1991). Although the verdict form in McNeil did not require unanimity for mitigating circumstances, the North Carolina Supreme Court found McKoy error because the trial court’s instructions could easily have misled the jurors into believing they could find no mitigating circumstance except by unanimous vote:
In its charge to the jury at the conclusion of the sentencing proceeding, the trial court used the word “unanimous” no less than thirteen times while instructing the jury concerning the two “Issues and Recommendation as to Punishment” forms that the jury was to complete. In the final mandate, the trial court instructed the jury that: “Your decision, your answers to any of the issues as to your final recommendation must be unanimousAfter the jurors had deliberated for approximately one day, the trial court inquired as to their progress. During that inquiry, the trial court stated: “Now as I indicated in my instructions to you, of course your answers to each of the issues must be unanimous in your recommendation in each case.” Although the trial court never explicitly stated that the jury had to be unanimous concerning mitigating circumstances under Issue Two on the forms used, the trial court stated at least three times that the jury’s answers to all the issues must be unanimous.
Id. 395 S.E.2d at 109. Thus, in the context of the overall charge, “the jury instructions gave rise to a reasonable likelihood that some of the jurors were prevented from considering constitutionally relevant evidence.” Id. at 110.
The State distinguishes Smith’s case from McNeil and analogizes it to Maynard v. Dixon, 943 F.2d 407 (4th Cir.1991), cert. denied, — U.S. -, 112 S.Ct. 1211, 117 L.Ed.2d 450 (1992), in which the Fourth Circuit found no McKoy error. Maynard is similar to McNeil in that the verdict form in neither case required a unanimous vote for mitigating circumstances; it is different, however, in that the Maynard trial court did not instruct the jury to answer all questions unanimously. Id. 943 F.2d at 420. Therefore, the Maynard court was satisfied that the sentencing instructions had not precluded a juror from considering mitigating circumstances that he or she, but not all the jurors, deemed relevant. Id. Because we find Smith’s case more like Maynard than McNeil, we reject Smith’s argument that McKoy error occurred during his sentencing hearing.
The sentencing instructions in Smith’s case, like those in Maynard, omitted a general unanimity charge. The jury was told that it had to vote unanimously on Issues One (presence of aggravating circumstances), Three (aggravating factors outweigh mitigating factors), and Four (aggravating circumstances are severe enough to warrant death). The jury was not told, however, that it had to vote unanimously on Issue Two (presence of mitigating factors). In discussing Issue Two, the trial court explained each of the five potential mitigating circumstances, and told *679the jurors that they were to write “Yes” on the verdict form beside each mitigating circumstance for which “the defendant has satisfied you” of its existence. On Issue Three the court instructed: “The question is whether ... the weight of the circumstances you find to exist, as to whether those which are aggravating outweigh in your minds the mitigating circumstances” (emphasis added). On Issue Four it instructed the jurors to “weigh all the circumstances that you have found, if any, to be aggravating, those that you’ve found to be mitigating, and determine whether you find beyond a reasonable doubt that the aggravating circumstances found by you are ... sufficiently important, to call for the imposition of the death penalty” (emphasis added). Like Maynard and unlike McNeil, the court in Smith’s case did not instruct the jurors that they could find the existence of a mitigating circumstance only by unanimous vote. Nor did the sentencing arguments of counsel include misleading statements. Accordingly, we find that Smith’s sentencing hearing was not tainted by McKoy error.
B.The “Recommendation” Claim
Smith’s remaining assignments of error in his cross-appeal have little merit. First is his argument that the trial court violated Caldwell v. Mississippi 472 U.S. 320, 105 S.Ct. 2633, 86 L.Ed.2d 231 (1985),16 when it referred to the jury’s decision whether to impose death as a “recommendation.” As the district court correctly noted, Caldwell does not apply retroactively because it created a new rule under Teague v. Lane, 489 U.S. 288, 109 S.Ct. 1060, 103 L.Ed.2d 334 (1989). Sawyer v. Smith, 497 U.S. 227, 235, 110 S.Ct. 2822, 2828, 111 L.Ed.2d 193 (1990). Moreover, even if Caldwell did apply retroactively, we have previously rejected Smith’s argument in a similar case. Gaskins v. McKellar, 916 F.2d 941, 953 (4th Cir.1990), cert. denied, — U.S. - , 111 S.Ct. 2277, 114 L.Ed.2d 728 (1991).
C. The Claim of Ineffective Assistance on Appeal
Next, Smith contends that his appellate counsel rendered ineffective assistance by failing to present three significant claims on direct appeal: the vagueness issue, the Caldwell “recommendation” issue, and the trial court’s sustaining an objection to a hypothetical question posed by Smith’s attorney to the State’s pathologist (see infra). Even if we were to assume that counsel’s failure to raise these claims on direct appeal violated the first prong of the Strickland test by being unreasonable, Smith clearly has not met the second requirement of Strickland: there is not a reasonable probability that the result in Smith’s case would have been different had his attorney raised these claims, since we reject all three on the merits. See Strickland v. Washington, 466 U.S. 668, 688-95, 104 S.Ct. 2052, 2064-68, 80 L.Ed.2d 674 (1984).
D. The Claim of Ineffective Assistance at Trial
Smith’s argument that his trial counsel rendered ineffective assistance is likewise weak. He contends that his attorneys insufficiently investigated and presented his defense during the guilt stage of the trial, and that they insufficiently developed and presented mitigating evidence during the sentencing stage. We are unpersuaded. We agree with the district court that the North Carolina superior court’s factual findings on this issue are supported by the record evidence. See Smith, 766 F.Supp. at 1387. Under the reasoning of the district court, id. at 1388-91, we affirm the holding that counsel’s efforts during the sentencing stage of Smith’s trial did not violate Strickland, and we agree with the reasoning of the superior court, State v. Smith, Nos. 80 CRS 15265, 15266, 15271, at 27-31 (N.C.Super.Ct. Dec. 16, 1983), which the district court approved, see Smith, 766 F.Supp. at 1396, that counsel’s efforts during the investigation stage did not violate Strickland.
*680E. The Cross-Examination Claim
Smith’s final challenge on cross-appeal is that the trial court violated his Sixth Amendment right to cross-examine a witness by sustaining an objection to a hypothetical question posed by Smith’s attorney to the State’s pathologist. The pathologist testified that Whelette Collins’s injuries were consistent with blunt trauma caused by a cinder-block. On cross-examination, when Smith’s attorney asked whether the injuries were also consistent with a fall from a twenty-foot cliff, the State’s attorney objected, saying, “[T]here’s no evidence of that.” In fact, witnesses for the State had already testified that the crime scene contained a twenty-foot cliff, at the foot of which lay broken rocks. The court sustained the objection. Again, we are unpersuaded by Smith’s contention that the court’s action was reversible error. After the court sustained the objection, Smith’s attorney rephrased the question, asking whether Collins’s head injuries “could have been caused by a fall.” The doctor testified that it was possible, though unlikely. Defense counsel asked whether there were “circumstances under which [the types of injuries Collins sustained] could be caused by a fall,” and the witness answered, “That’s possible, yes.” Smith’s attorney used this information in his closing argument. Referring to the twenty-foot cliff and to “some rocks [below] that had blood on [them],” he argued that Collins had died by accidentally falling over the cliff. Assuming the trial court’s decision to sustain the State’s objection was erroneous, it was harmless beyond a reasonable doubt because Smith’s attorney elicited from the pathologist the information he sought: that Collins’s injuries could have been caused by a fall. See Gaskins v. McKellar, 916 F.2d 941, 950 (4th Cir.1990).
V.
In conclusion, we affirm the district court’s grant of habeas ■ relief because the North Carolina Supreme Court on direct appeal did not cure the unconstitutionally vague sentencing instruction on the aggravating factor relating to an “especially heinous, atrocious or cruel” murder. We also affirm the district court’s rejection of Smith’s other claims for relief.
AFFIRMED.
. 28 U.S.C. § 2254.
. The order stated:
This matter was heard on a paperwriting entitled "Motion for Appropriate Relief" filed June 6, 1983 by [Smith’s attorneys].
The court has read the paperwriting and considered the arguments in support of the claims set out therein. The court finds as a fact that the Claims No. I, II, III, and IV, set forth no probable grounds for relief.
It is concluded that the matters alleged in Claim[] No. V constitute a sufficient showing to require a plenary hearing....
NOW THEREFORE, IT IS ORDERED THAT:
1. Claims No. I, II, III, and IV are denied.
2. A plenary hearing in Claim[] No. V is to be held.
. Smith then filed a second Motion for Appropriate Relief in North Carolina superior court. This motion raised ineffectiveness of counsel in conceding Smith’s guilt at trial and in admitting to the existence of certain aggravating circumstances. The superior court denied the motion, State v. Smith, Nos. 80 CRS 15265, 15266, 15271 (N.C.Super.Ct. Mar. 9, 1987). The Supreme Court of North Carolina denied certiorari, State v. Smith, 364 S.E.2d 668 (N.C.1988), as did the United States Supreme Court, Smith v. North Carolina, 485 U.S. 1030, 108 S.Ct. 1589, 99 L.Ed.2d 903 (1988).
. For simplicity, we refer to the reviewability of the heinousness issue only. The State argues that Smith defaulted on two additional claims (described infra): the McKoy claim, and the claim regarding Smith’s cross-examination of the pathologist. We find none of these three claims procedurally barred.
. Although the North Carolina Supreme Court denied certiorari following the superior court's decision on Smith's motion, we have held that the "last state court judgment" for Coleman purposes is the superior court’s denial of the Motion for Appropriate Relief, not the North Carolina Supreme Court's denial of certiorari. Felton v. Barnett, 912 F.2d 92, 94-95 (4th Cir.1990), cert. denied, 498 U.S. 1032, 111 S.Ct. 693, 112 L.Ed.2d 683 (1991); see also Ylst v. Nunnemaker, — U.S.-,-n. 2, 111 S.Ct. 2590, 2594 n. 2, 115 L.Ed.2d 706 (1991) (noting that denial of certiorari is not a judgment).
. Section 15A-1419(a) lists three bases for denying a motion for appropriate relief. Additionally, a state court in receipt of a motion subject to denial under 15A-1419(a) may choose to review the substance of the motion and deny it on the merits. See, e.g., State v. Price, 331 N.C. 620, 418 S.E.2d 169, 174-75 (1992) (After noting that defendant's motion for appropriate relief was "subject to being dismissed” under § 15A-1419(a)(3) because the two arguments contained in the motion could have been raised in defendant's original appeal, supreme court "nevertheless elected to review” the arguments "in the interests of both judicial economy and thorough scrutiny of this capital case,” and rejected the merits of both.), vacated,-U.S.-, 113 S.Ct. 955, 122 L.Ed.2d 113 (1993). Therefore, Smith's heinousness claim was rejected either under § ISA-1419(a)(3) because it was procedurally barred, or on the merits.
. Both this circumstance and the language of the superior court’s order weigh heavily in favor of finding that the superior court decided the merits of Claims I-IV.
. Byrd v. Delo, 942 F.2d 1226 (8th Cir.1991), holds that timing can reveal the basis for a court's order. The Byrd court concluded that an ambiguously worded rejection of a defendant's petition was based on procedural grounds, because the order was issued on the same day the petition was filed. The short turnaround indicated the lower court had not taken the time to examine the petition on the merits. Id. at 1232, distinguished in Nickerson, 971 F.2d at 1129 n. 5.
. The dissent maintains that Smith could have raised this issue in his direct appeal. Dissenting opinion at 683. That would have been impossible, since the gist of Smith’s argument is that he was denied the effective assistance of counsel in his direct appeal:
[T]hc North Carolina Supreme Court, at the time it considered and decided defendant's case on appeal, had not provided for any clear and regular system of appellate sentence review, nor had it disclosed what standards governed its discharge of its statutory duty. As of the date defendant's case was reviewed by the Court, over four years had elapsed since the effective date of the punishment statute without any indication from the Court of the standards that would guide counsel in effectively representing their clients on an issue of, literally, life or death.
Without any articulated standards for review, defendant's counsel was unable adequately to prepare or to present argument to the Court on the proportionality issue, rendering meaningless defendant's Sixth Amendment right to the assistance of counsel for his appellate defense.
Motion for Appropriate Relief, Nos. 80 CRS 15265, 15266, 15271, at 5758 (N.C.Super.Ct. filed June 6, 1983) (citation omitted).
. Section 15A-1419(a)(2) provides that a Motion for Appropriate Relief may be denied when "[t]he ground or issue underlying the motion was previously determined on the merits upon an appeal from the judgment.” For purposes of federal habeas review, a denial under this section is clearly based on the merits, not on procedural default. See Coleman,-U.S. at-, 111 S.Ct. at 2554 (stating that a defendant is procedurally barred when he fails to meet a state procedural requirement through his error). As the official commentary to § 15A-1419 makes clear, (a)(2) provides that "if a matter has been determined on the merits upon an appeal, ... there is no right to litigate the matter again in a[] ... motion for appropriate relief (emphasis added). There remains, of course, the right to litigate the matter before a federal habeas court. A denial under (a)(2) is a holding that the state has addressed the federal claim on the merits. Because the state's ruling is based on grounds that are not independent of the federal claims, there is no basis to apply the independent and adequate state grounds doctrine, which ”bar[s] federal ha-beas when [the state] declined to address a prisoner's federal claims.” Coleman, - U.S. at -, 111 S.Ct. at 2554 (emphasis added).
As the Supreme Court has revealed, if the last explained state judgment (here, Smith's direct appeal) fairly appears to rest primarily on federal law, the federal court should "presume that no procedural default has been invoked by a subsequent unexplained order that leaves the judgment or its consequences in place.” Ylst v. Nunnemaker,-U.S.-,-, 111 S.Ct. 2590, 2594, 115 L.Ed.2d 706 (1991). Under this "look-through” presumption, the federal habeas court " 'looks through' [the unexplained order] to the last reasoned decision.” Id. at-, 111 S.Ct. at 2595. Overcoming the presumption requires "strong evidence.” Id. For example, unlike here "it might be shown that, even though the last reasoned state-court opinion had relied upon a federal ground, the later appeal to the court that issued the unexplained order was plainly out of time, and that the latter court did not ordinarily waive such a procedural default without saying so.” Id. at -, 111 S.Ct. at 2596; see James S. Liebman & Randy Hertz, Federal Habeas Corpus Practice and Procedure § 24.2(e), at 316-17 (1992 Supp.).
As further support for the proposition that a denial under § 15A1419(a)(2) is substantive, not procedural, for purposes of federal habeas review, the official commentary states that the provision is based on N-Y.Crim.Proc.Law 440.10, which the Second Circuit has interpreted as creating a ruling on the merits. See Silverstein v. Henderson, 706 F.2d 361, 368 (2d Cir.) (State court's denial of collateral relief under § 440.-10(2)(a) following state appellate court’s rejection of defendant’s federal claim on the merits "does not constitute a finding of procedural default that would bar federal consideration of Sil-verstein’s claims.”), cert. denied, 464 U.S. 864, 104 S.Ct. 195, 78 L.Ed.2d 171 (1983); accord Maxwell v. Sumner, 673 F.2d 1031, 1034 (9th Cir.) (applying California law), cert. denied, 459 U.S. 976, 103 S.Ct. 313, 74 L.Ed.2d 291 (1982).
. The State also concedes that Maynard applies retroactively. See Stringer v. Black, - U.S. -, -, 112 S.Ct. 1130, 1135, 117 L.Ed.2d 367 (1992) (holding that Maynard did not create a new rule under Teague v. Lane, 489 U.S. 288, 109 S.Ct. 1060, 103 L.Ed.2d 334 (1989)).
. The Supreme Court has found this definition constitutional. Proffitt v. Florida, 428 U.S. 242, 255-56, 96 S.Ct. 2960, 2968, 49 L.Ed.2d 913 (1976).
. The Brecht Courl held that constitutional errors of the "trial” type are subject to a lower standard of harmless-error analysis on federal habeas review (error must not cause "actual prejudice,” see Kotteakos v. United States, 328 U.S. 750, 776, 66 S.Ct. 1239, 1253, 90 L.Ed. 1557 (1946)) than on direct appeal (error must be harmless beyond a reasonable doubt, see Chapman v. California, 386 U.S. 18, 24, 87 S.Ct. 824, 828, 17 L.Ed.2d 705 (1967)). Brecht, - *677U.S. at-, 113 S.Ct. at 1721-22. Thus, Brecht created the following anomaly: If a state court conducts harmless-error review of a constitutional error, the defendant has the advantage of the State having to prove harmlessness beyond a reasonable doubt. If, however, the state court does not discover the error (as here), or does not review it for harmlessness (as here), the defendant is handicapped, since, on federal habeas review, the State has only to establish that the error did not “substantially prejudice” the jury's decisión. See id. at -, 113 S.Ct. at 1725 (White, J., dissenting) (explaining the "illogically disparate treatment” caused by Brecht).
The Supreme Court recently indicated that the lower Brecht standard of review applies to federal habeas review of capital sentencing errors. Applying the Chapman standard on habeas review, the Eleventh Circuit had found an invalid aggravating factor not harmless; the Supreme Court vacated the decision and remanded it for further consideration in light of Brecht. See Singletary v. Duest, — U.S. -, 113 S.Ct. 1940, 123 L.Ed.2d 647 (1993), vacating 967 F.2d 472 (11th Cir.1992); see also Singletary v. Smith, — U.S. -, 113 S.Ct. 1940, 123 L.Ed.2d 646 (1993), vacating 970 F.2d 766 (11th Cir.1992). Notably, however, the Eleventh Circuit had not conducted harmless-error analysis in the first instance; it had reviewed a decision by the Florida Supreme Court finding the error harmless. That is not the case here.
The Supreme Court’s repeated references to state court harmless-error review of invalid aggravating factors indicate that it meant for state courts to conduct such review in the first instance. Therefore, it intended not to apply the Brecht anomaly in cases tainted by invalid aggravating factors. We observe the Court's intention through the approach we adopt today. By holding that the North Carolina state courts are the only courts with the authority to conduct harmless-error analysis of the vagueness error in Smith's case in the first instance, we, avoid the possibility of a federal habeas court reviewing the error in the first instance under the lower "actual prejudice” standard. This approach not only is counseled by language in several Supreme Court opinions, it also ensures reliability, which is of paramount importance in capital cases, see, e.g., Herrera v. Collins, -U.S.-, -, 113 S.Ct. 853, 863, 122 L.Ed.2d 203 (1993), and promotes fundamental fairness for defendants whose death sentences have been tainted by invalid aggravating factors. See Brecht, - U.S. at -, 113 S.Ct. at 1729 (O'Connor, J., dissenting).
. McKoy and Mills apply retroactively. Williams v. Dixon, 961 F.2d 448, 456 (4th Cir.), cert. denied, — U.S. -, 113 S.Ct. 510, 121 L.Ed.2d 445 (1992). Because the district court ruled on Smith's habeas petition before we issued our opinion in Williams, it mistakenly concluded that no McKoy error could be found in Smith’s case because McKoy did not apply retroactively. See Smith, 766 F.Supp. at 1377-78.
. The verdict form in Smith's case asked the jury to answer four questions: (1) whether it unanimously found any of the four aggravating circumstances listed on the form, (2) whether it found any of the five mitigating circumstances listed on the form, (3) whether it unanimously found heyond a reasonable doubt that the aggravating circumstances outweighed the mitigating circumstances, and (4) whether it unanimously found beyond a reasonable doubt that the aggravating circumstances were substantial enough to warrant the death penalty.
. Under Caldwell, “it is constitutionally impermissible to rest a death sentence on a determination made by a sentencer who has been led to believe that the responsibility for determining the appropriateness of the defendant’s death rests elsewhere." 472 U.S. at 328-29, 105 S.Ct. at 2639.