Vacated and remanded by published opinion. Judge MOTZ wrote the opinion, in which Judge MICHAEL joined. Judge NIEMEYER wrote a dissenting opinion.
OPINION
DIANA GRIBBON MOTZ, Circuit Judge:Concluding that Linda Plemons had not received constitutionally adequate notice of her right to redeem certain real property, the district court granted summary judgment to Plemons and set aside a deed to that property obtained through the state tax-sale procedure. Advantage 99 TD, the tax lien purchaser, and Douglas Q. Gale, who subsequently acquired the deed from Advantage, appeal, asserting that constitu*571tionally sufficient notice was provided to Plemons. For the reasons that follow, we vacate the judgment of the district court and remand for further proceedings consistent with this opinion.
I.
In August 1999, Linda Plemons and her business partner, Jerry Lipscomb (who is not a party to this appeal) purchased the property in question, located on Echo Road in South Charleston, West Virginia, for $55,000. They duly recorded the deed.
In February 2000, .Plemons obtained financing from Capital State Bank in the amount of $45,000 to pay off the seller of the property. She mistakenly believed that the bank was paying the property taxes on the property through an escrow account. Because neither she nor the bank actually paid the taxes, the Sheriff of Kanawha County sold a tax lien on the property to Advantage 99 TD on November 13, 2000. Plemons was unaware of the sale when, in May 2001, she moved from the property and rented it to tenants.
In December 2001, Advantage sought the issuance of a tax deed. As required by West Virginia law, Advantage “[p]re-pare[d] a list of those to be served with notice to redeem” and filed that list with the Clerk of Kanawha County so that the Clerk could send them notice of their right to redeem the tax lien. See W. Va.Code Ann. § 11A-3-19 (Michie 2002).
The list enumerated several interested parties, including Plemons, and provided three addresses for Plemons: 913 Echo Road, South Charleston, the address of the subject property in the relevant deeds; 917 Echo Road, South Charleston, the mailing address of the property; and 928 Garden Street, Charleston, the address of another property owned by Plemons. The list -also directed the Clerk to send notices to “Occupant” at 913 and 917 Echo Road. In late January 2002, the Clerk sent the notices by certified mail return receipt requested. The parties agree that the Post Office promptly returned as' undeliverable the notices addressed to Plemons, as well as the notices sent to Occupant at the Echo Road addresses.1 Plemons had been renting out the subject property and living on Quarry Pointe since November 2001.
After return of the mailed notices, Advantage published, from April 12, 2002 to April 26, 2002, notice as to redemption rights in two Charleston newspapers and posted the notice on the front door of the Kanawha County courthouse. No one responded to the publications or posting. On May 7, 2002, the Clerk issued a deed to Advantage, .which it recorded. On November 22, 2002, Advantage conveyed the property to Douglas Q. Gale by quitclaim deed, which he properly recorded. According to Plemons,. she first became aware of the sale of the property in January 2003.
II.
■ Challenging her failure to receive timely notice as a violation of state law and the United States Constitution, Plemons filed a complaint in West Virginia state court seeking to set aside the tax deed issued to Advantage as well as the deed issued to Gale. Advantage, a Delaware business trust, and Gale, a citizen and resident of *572Florida, removed the case to federal court on the basis of diversity jurisdiction.
On Plemons’ motion for summary judgment, the district court examined West Virginia’s statutory scheme for tax sales of property. Section 11A-3-22 provides in relevant part:
As soon as the clerk has prepared the notice ..., he shall cause it to be served upon all persons named on the list generated by the purchaser....
If the address of any person entitled to notice ... is unknown to the purchaser and cannot be discovered by due diligence on the part of the purchaser, the notice shall be served by publication....
W. Va.Code Ann. § 11A-3-22 (Michie 2002). A related provision of West Virginia law allows a person to set aside a tax-sale deed if she shows “by clear and convincing evidence” that the purchaser “failed to exercise reasonably diligent efforts to provide notice of his intention to acquire such title to the complaining party.” W. Va Code Ann. § 11 A-4-4(b) (Mi-chie 2002).
The district court interpreted these West Virginia statutes to require a purchaser to exercise due diligence in identifying and locating parties entitled to notice and to allow publication notice only after the exercise of such diligence. The court, therefore, properly reasoned that West Virginia’s statutory notice requirements parallel the requirements of the United States Constitution. See Mennonite Bd. of Missions v. Adams, 462 U.S. 791, 103 S.Ct. 2706, 77 L.Ed.2d 180 (1983); Mullane v. Central Hanover Bank & Trust Co., 339 U.S. 306, 70 S.Ct. 652, 94 L.Ed. 865 (1950),2
The court concluded that “[wjhen notice sent by certified mail is returned unclaimed, the reasonable diligence standard requires the purchaser to make further inquiry reasonably calculated to locate the interested party’s correct address.” The district court found that in this case, after return of the notices, Advantage “could have ascertained Ms. Plemons’ address through a number of different means”— telephoning her at the number listed in the local telephone directory, asking Plemons’ tenants for their assistance in reaching her, or inquiring of Plemons’ mortgagee. Because Advantage took “none of these actions” to find Plemons after the notices were returned as undeliverable, the court held that Plemons had proved that she had not received constitutionally adequate notice of the right to redeem her property and granted her summary judgment.
Advantage and Gale appeal. They do not maintain that they are entitled to summary judgment. But they do assert that the district court erred in granting summary judgment to Plemons.
III.
We must determine whether, as a matter of law, Plemons failed to receive constitutionally sufficient notice before the issuance of the tax-sale deed that extinguished her property interest.3
*573A.
In a series of cases, beginning with Mullane v. Central Hanover Bank & Trust Co., the Supreme Court has set forth the requirements for constitutionally adequate notice of an impending deprivation of property. “[I]n any proceeding which is to be accorded finality,” due process requires “notice reasonably calculated, under all the circumstances, to apprise interested parties of the pendency of the action and afford them an opportunity to present their objections.” Mtdlane, 339 U.S. at 314, 70 S.Ct. 652.
Mullane dealt with notice by publication to beneficiaries of a common trust. Complying with the New York law governing such trusts, Central Hanover Bank published notice in a local newspaper to inform beneficiaries of a settlement. In addressing the sufficiency of this notice, the Supreme Court emphasized, that “when notice is a person’s due, process which is a mere gesture is not due process.” Id. at 315, 70 S.Ct. 652. Rather, the means used to provide notice “must be such as one desirous of actually informing the absentee might reasonably adopt to accomplish it.” Id. Only a method that is reasonable, taking into account “the practicalities and peculiarities of the case,” will be adequate. Id. at 314-15, 70 S.Ct. 652. The Court held that notice by publication sufficed for those beneficiaries “whose interests or whereabouts could not with due diligence be ascertained.” Id. at 317, 70 S.Ct. 652. But notice by publication did not suffice for those identifiable beneficiaries whose location was ascertainable; that class of beneficiaries should have been notified by mail. Id. at 318, 70 S.Ct. 652 (“Where the names and post office addresses .:. are at hand, the reasons disappear for resort to means less likely than the mails.... ”).
Cases following Mullane have sharpened its rule, but reasonable efforts designed to “actually inform[]” a party with a property interest of possible deprivation of that interest remain the touchstone of constitutionally adequate notice. Id. at 315, 70 S.Ct. 652. Thus, although the Constitution does not always require actual receipt of notice, it does always require efforts “reasonably calculated under all the circumstances to apprise” a party “of the pendency” of the deprivation of property. Dusenbery v. United States, 534 U.S. 161, 168-171, 122 S.Ct. 694, 151 L.Ed.2d 597 (2002). When a party required to give notice knows that a mailed notice has, for some reason, failed to inform a person holding a property interest of the impending deprivation, the notice does not pass constitutional muster. See Robinson v. Hanrahan, 409 U.S. 38, 40, 93 S.Ct. 30, 34 L.Ed.2d 47 (1972) (holding notice of forfeiture sent to address State knew to be inaccurate or defective insufficient); Covey v. Town of Somers, 351 U.S. 141, 146-47, 76 S.Ct. 724, 100 L.Ed. 1021 (1956) (holding notice mailed to taxpayer known to be incompetent insufficient to afford her notice).
Of course, “consideration should be given to the practicalities of the situation” in each case. Tulsa Prof'l Collection Servs., 485 U.S. at 489-90, 108 S.Ct. 1340. However, “actual notice is a minimum constitutional pre-condition to a proceeding *574which will adversely affect the liberty or property interests of any party, whether unlettered or well versed in commercial practice, if its name and address are reasonably ascertainable.” Id. at 485, 108 S.Ct. 1340 (internal quotation marks and citation omitted). For this reason, the Court has held that even a state’s “legitimate interest in expeditious resolution” of probate proceedings does not justify the failure to mail notice of a “nonclaim” probate proceeding to a creditor when the identity of the creditor was “reasonably ascertainable” through “reasonably diligent efforts.” Id. at 489, 491, 108 S.Ct. 1340.
In 1983 the Court considered application of these principles in the context of a tax sale, specifically, whether “constructive notice by publication” to a mortgagee sufficed to inform the mortgagee of a pending tax sale of property in which it had an interest. Mennonite, 462 U.S. at 798, 103 S.Ct. 2706. The Court held that when the identity and location of a mortgagee can be obtained through examination of public records, “constructive notice alone does not satisfy the mandate of Mullane.” Id. Moreover, “a party’s ability to take steps to safeguard its interests does not relieve the State of its constitutional obligation.” Id. at 799, 103 S.Ct. 2706. Although a party required to provide notice need not “undertake extraordinary efforts to discover ... whereabouts ... not in the public record,” it must use “reasonably diligent efforts” to discover addresses that are reasonably ascertainable. See id. at 798 & n. 4,103 S.Ct. 2706.
In sum, Mullane and its progeny teach that a party charged with giving notice must be reasonably diligent in doing so. In the case of a tax sale of propei'ty, diligence requires that reasonable efforts be made to identify and locate parties with an interest in the property. Once those parties are located, they must be provided notice of the impending sale using a method reasonably calculated, under all of the circumstances, to actually inform them of the sale.
B.
Here, Advantage examined the title to the property to identify and locate those with interests in it'and then arranged to send notice by certified mail return receipt requested to the addresses that it found. Each of the notices addressed to Plemons (or to Occupant of the subject property) was promptly returned as undeliverable. The question before us is what efforts must be made by a party charged with giving notice of irrevocable loss of property via a tax- sale, when it is, or should be, apparent from the initial mailings’ prompt return that they have failed to provide any notice to the intended recipient.
Although the Supreme Court has not directly addressed this question, it has provided some guidance in Covey and Robinson. In Covey, 351 U.S. at 146-47, 76 S.Ct. 724, when a town had mailed notice of its intent to foreclose on a tax lien to a person whom the town knew to be mentally incompetent, the Court held that such notice was constitutionally insufficient. Because the town was aware that, as a consequence of the incompetence, the mailing did not actually provide notice, the foreclosure constituted a deprivation of property without due process of law. See also Robinson, 409 U.S. at 40, 93 S.Ct. 30 (holding that mailing that the government knew would not accomplish notice was insufficient). These cases, as one state supreme court has noted, “suggest that when the party seeking to affect a property interest is itself on notice of the failure of mailed notice to inform an interested party, the party must take further action to determine a more accurate address or oth*575erwise ensure receipt of- meaningful notice.” Schwartz v. Dey, 665 S.W.2d 933, 935 (Mo.1984) (en banc). Adopting the rule that prompt return of mailed notice triggers a duty to make reasonable followup efforts would seem to best comport with the instruction in Mullane that due process requires efforts “reasonably calculated” to actually “apprise interested parties” of the possible deprivation; that -is, notice consistent with that of “one desirous of actually informing the absentee,” rather than efforts that are but a “mere gesture.” Mullane, 339 U.S. at 314-15, 70 S.Ct. 652.
Most courts have reached precisely this conclusion.4 In case after case they have held that the reasonable diligence standard' requires a party charged with notice to follow up when a mailing has been returned as unclaimed or undeliverable. As the District of Columbia Court of Appeals has remarked, “The return of the certified notice marked ‘unclaimed’ should have been a red flag for some further action.” Malone v. Robinson, 614 A.2d 33, 38 (D.C. 1992); see also Bank of America v. Giant Inland Empire R.V. Ctr., Inc., 78 Cal.App.4th 1267, 93 Cal.Rptr.2d 626, 635 (2000) (“[Ojnce County became aware that Bank had not received notice regarding the tax sale, ... County should have made reasonable efforts to renotify Bank about the tax sale at an alternate address.”).
The Supreme Court of Pennsylvania, in Tracy v. County of Chester, Tax Claim Bureau, reminds that “it is a momentous event ... when a government subjects a citizen’s property to forfeiture for the non-payment of taxes.”. 507 Pa. 288, 489 A.2d 1334, 1339 (1985); see also St. George Antiochian Orthodox Christian Church v. Aggarwal, 326 Md. 90, 603 A.2d 484, 490 (1992) (noting “the importance of the property right that is involved in the foreclosure of a right of redemption”). Because of the importance of the property right, “due process ... requires at a minimum that an owner of land be actually notified by government, if reasonably possible, before his land is forfeited by the state.” Tracy, 489 A.2d at 1339. Thus, “where the mailed notice has not been delivered because of an inaccurate address, the authority must make a reasonable effort to ascertain the identity and whereabouts ' of the owner(s).” Id. at 1338-39.' Similarly, the New York Court of Appeals has explained that, when notice is returned as undeliverable, “the enforcing officer is in no different position than if an initial examination of the [tax] roll had yielded no address. Generally; when the notice is returned as undeliverable, the tax district should conduct a reasonable search of the public record.” Kennedy v. Mossafa, 100 N.Y.2d 1, 759 N.Y.S.2d 429, 789 N.E.2d 607, 611 (2003).
Indeed, the courts so holding are legion. See, e.g., Akey v. Clinton County, 375 F.3d 231, 236 (2d Cir.2004) (“In light of the notice’s return, the County was required to use ‘reasonably diligent efforts’ to ascertain [the] correct address.”); Rosenberg v. *576Smidt, 727 P.2d 778, 781-83 (Alaska 1986) (requiring, in a case in which notice was returned as unclaimed, the exercise of due diligence to determine a correct address); Schmidt v. Langel, 874 P.2d 447, 450 (Colo.Ct.App.1993) (“ ‘Diligent inquiry’ requires that if a notice has been returned, the county treasurer must re-examine the county records to check the address for accuracy and look for an alternative address.”); Giacobbi v. Hall, 109 Idaho 293, 707 P.2d 404, 408-09 (1985) (holding that the return of mailed notice as undelivered imposed a duty on the county to make reasonable inquiry to find the owner’s correct address); Bryant v. T.C.B. Enters., 395 So.2d 823, 825-26 (La.CtApp.1981) (requiring, after mailed notice was returned, further effort on the part of the tax collector to inform tax debtors of delinquent taxes); St. George Antiochian Orthodox Christian Church, 603 A.2d at 490-91 (holding that when the initial investigation of the tax rolls provided the incorrect address, and notice was returned as undeliverable, the parties should have made efforts to discover the correct address); City of Boston v. James, 26 Mass.App.Ct. 625, 530 N.E.2d 1254, 1256 (1988) (requiring further inquiries when notice was returned); Patrick v. Rice, 112 N.M. 285, 814 P.2d 463, 468 (Ct.App.1991) (holding that the return of mailed notice did not mean that the correct address was not reasonably ascertainable and voiding the tax sale in which the property at issue was sold); O’Brien v. Port Lawrence Title & Trust Co., 688 N.E.2d 1136, 1145 (Ohio Ct. Common Pleas 1997) (ruling that the county’s failure to follow up once notice was returned as undeliverable “fell far short o.f the reasonable diligence required”); Wells Fargo Credit Corp. v. Ziegler, 780 P.2d 703, 705 (Okla.1989) (holding, in a case in which the county treasurer mailed notice, but the proof of receipt was never received by the treasurer, “the act of mailing without proof of receipt of notice falls short of the exercise of reasonable diligence in assuring actual notice”); Good v. Kennedy, 291 S.C. 204, 352 S.E.2d 708, 711 (Ct.App.1987) (holding that, when notice was returned undelivered, diligence required further efforts to uncover a correct address).
Likewise, many of our sister circuits, in a different but analogous context, have required that the party charged with notice follow up once it is clear that initial mailings have failed to provide notice. See United States v. Ritchie, 342 F.3d 903, 911 (9th Cir.2003) (“We now join [the Second, Third, Fifth, Seventh, Tenth, and D.C.] [CJircuits in holding that, when initial personal notice letters are returned undelivered, the government must make reasonable additional efforts to provide personal notice.”).
As all of these cases recognize, initial reasonable efforts to mail notice to one threatened with loss of property will normally satisfy the requirements of due process. However, when prompt return of an initial mailing makes clear that the original effort at notice has failed, the party charged with notice must make reasonable efforts to learn the correct address before constructive notice will be deemed sufficient. “A reasonable person presented with a letter that has been returned to sender will ordinarily attempt to resend it if it is practicable to do so.” Small v. United States, 136 F.3d 1334, 1337 (D.C.Cir.1998). Thus, the district court properly held that the reasonable diligence standard mandated by Mullane and its progeny required some followup effort here.5
*577c.
However, a tax sale" need not be set aside in every case in which initial attempts at mailed notice have failed and no further mailed notice is sent. Mullóme instructs that “all the circumstances” of a case, including its “practicalities and peculiarities,” must be considered in determining the constitutional sufficiency of notice. 339 U.S. at 314, 70 S.Ct. 652. There may be instances when reasonable follow-up efforts would yield no different address; and the Constitution only requires reasonable efforts, given all of the circumstances of a particular case, not receipt of actual notice.
In this case, the district court considered several possible follow-up efforts. Although it initially noted that checking the public records would be reasonable, the court does not seem to have determined if that was done here. Instead, the court pointed to three other methods it believed Advantage reasonably could have, but did not, pursue to obtain Plemons’ address after receiving the returned mailings: consulting the telephone directory, asking the tenants at the Echo Road property, or making inquiries of the mortgagee bank. We do not agree that reasonable follow-up compelled such efforts in this case. Although checking the local telephone directory may be reasonable in a given situation, see Small, 136 F.3d at 1338 n. 3, here it would have been an exercise in futility. The record shows that, both at the time the notices were sent out,.as well as when they were returned, Plemons was not reachable at the number or address listed in the current directory, and calls to that number were no longer being forwarded to her mobile phone. Moreover, contacting the Echo Road tenants seems an unreasonable burden here. Because it is undisputed that the notice sent to Occupant at the property’s mailing address was returned as undeliverable, it was a reasonable assumption that further investigation at that address would be unsuccessful. Nor do reasonable efforts require contacting the mortgagee bank, at least in this case. As the Supreme Court noted in Mennonite, a property owner and mortgagee are not in privity, and, under normal circumstances, one cannot be expected to communicate notice of an impending tax sale to the' other. 462 U.S. at 799, 103 S.Ct. 2706. There is no evidence that Plemons enjoyed a special relationship with the bank such that attempting to enlist its help would have led to the discovery of her correct location.
But, as the district court initially remarked, and as most cases addressing this situation recognize, it is, at the very least, reasonable to require examination (or reexamination) of all available public records when initial mailings have been promptly returned as undeliverable. See Akey, 375 F.3d at 237 (“ ‘[Extraordinary efforts’ typically describe searches beyond the public record, not searches of the public record.”); see also Rosenberg, 727 P.2d at 780; Sinclair & Valentine Co. v. County of Los Angeles, 201 Cal.App.3d 1021, 247 Cal. Rptr. 568, 570 (1988); Schmidt, 874 P.2d at 451; Giacobbi, 707 P.2d at 409; St. George Antiochian Orthodox Christian Church, 603 A.2d at 490; Fulton v. Cornelius, 107 N.M. 362, 758 P.2d 312, 316 (Ct. App.1988); Kennedy, 759 N.Y.S.2d 429, 789 N.E.2d at 612; O’Brien, 688 N.E.2d at 1144; Tracy, 489 A.2d at 1339. Requiring perusal of publicly available information does not subject the tax lien purchaser to *578the “impracticable and extended searches [that] are not required in the name of due process.” Mullane, 339 U.S. at 317-18, 70 S.Ct. 652.
Accordingly, reasonable diligence required Advantage to search all publicly available county records once the prompt return of the mailings made clear that its initial examination of the title to the Echo Road property had not netted Plemons’ correct address. Unfortunately, the record in this case does not disclose what efforts, if any, Advantage made to search public documents, or whether Plemons’ proper address would have been ascertainable from such a search. Thus, we must remand the case to the district court for resolution of these questions.
rv.
The district court’s order granting summary judgment to Plemons is vacated and remanded for further proceedings consistent with this opinion.
VACATED AND REMANDED
. Although the record does not disclose the precise date on which all of these notices were returned, all were returned well prior to publication and thé expiration of the redemption period. ‘ It is clear that the notice sent to Plemons at 928 Garden State w,as returned on February 14, 2002, and the notice sent to Occupant at 917 Echo Road was returned on February 17, 2002.
. For this reason, the court concluded that its resolution of the case obviated the need to examine the possible constitutional infirmity of West Virginia's requirement that a plaintiff prove the failure of adequate notice by clear and convincing evidence. To the extent that Advantage and Gale contend that the West Virginia statutes do, or could, require less exacting notice than that mandated by the Constitution, we reject their arguments.
. The Constitution only requires due process when the state or federal government works the deprivation of property. Appropriately, neither party disputes that the tax-sale procedure in this case constitutes state action, although state law charges a private party with *573providing notice. Under West Virginia's statutory scheme, the State is the initial seller of the tax lien; thereafter, the State provides the tax lien purchaser with the mechanism to provide notice to interested parties. The State also extinguishes the owner's rights to the property by issuing the tax deed to the property. In order to accomplish 'a tax sale, then, private parties must “make use of state procedures with the overt, significant assistance of state officials,” and, thus, there is state action. Tulsa Prof'l Collection Servs., Inc. v. Pope, 485 U.S. 478, 486, 108 S.Ct. 1340, 99 L.Ed.2d 565 (1988).
. A few cases hold to the contrary. See Tsann Kuen Enters. Co. v. Campbell, 355 Ark. 110, 129 S.W.3d 822 (2003); Smith v. Cliffs on the Bay Condominium Assoc., 463 Mich. 420, 617 N.W.2d 536 (2000); Dahn v. Trownsell, 576 N.W.2d 535 (S.D.1998); Hutchinson Island Realty, Inc. v. Babcock Ventures, Inc., 867 So.2d 528 (Fla.Dist.Ct.App.2004). We do not find them persuasive. None address, or even cite, the Supreme Court’s holdings in Covey and Robinson. Moreover, these contrary cases rely on a notion, rejected by the Supreme Court, that an interested party’s failure to protect its interests, such as by registering a corrected or new address with the government, relieves the party charged w$th notice of its constitutional duty to provide notice. See Mennonite, 462 U.S. at 799, 103 S.Ct. 2706 (“[A] parly’s ability to take steps to safeguard its interests does not relieve the State of its constitutional obligation.”) (emphasis added).
. We do not hold, nor does Plemons argue, that the West Virginia statutory scheme vio*577lates the Constitution. Rather, we hold that the statutory scheme, as interpreted by the district court, see supra note 2, "is constitutional. However, because it is unclear whether the reasonable diligence required by any constitutional scheme was exercised in the case at hand, we must remand for further proceedings.