COLLOTON, Circuit Judge.

Simone R. Taylor sought a writ of mandamus to compel the Social Security Administration ("SSA") to pay benefits to which she claims entitlement. The district court denied her motion. We affirm, although we note that an unexplored avenue of possible relief for Taylor remains available.

I.

Taylor was born in the United Kingdom in 1974 and remains a British citizen. She was adopted by citizens of the United States — an American serviceman and his wife — in the United Kingdom in 1984, and she moved to the United States with her adoptive family that year. According to photocopied documents included in the record, Taylor entered the United States on August 13, 1984. Her adoptive father filed a "Petition to Classify Status of Alien Relative for Issuance of Immigrant Visa," listing Taylor as a beneficiary. The petition was approved in September 1984, and Taylor was thus classified as an "immediate relative" of a United States citizen. See 8 U.S.C. §§ 1151(b)(2)(A)(i), 1154(a).

The visa petition records the date that Taylor's stay would expire as "indefinite," and states that "[b]eneficiary is in the United States and will apply for adjustment of status to that of a lawful permanent resident in the office of the Immigration and Naturalization Service at Kansas City, Missouri." A "Notice of Approval of Relative Immigrant Visa Petition," dated October 19, 1984, and completed by the Immigration and Naturalization Service in Kansas City, states that Taylor's adoptive father should "contact the above office for further information concerning the beneficiary's adjustment of status." The record includes no evidence concerning whether Taylor or anyone acting on her behalf ever applied for adjustment of status.

On June 28, 1998, Taylor filed an application for disability insurance benefits under Title II of the Social Security Act ("The Act"). Taylor's application was initially denied, but after a hearing, an administrative law judge ("ALJ") found that Taylor was disabled.

In November 1999, the SSA wrote to Taylor explaining that her application for disability benefits had been approved, but that the SSA could not pay her benefits for any month in which she was not lawfully present in the United States. This letter presumably was designed to implement a provision of the Illegal Immigration Reform and Immigrant Responsibility Act of 1996, which limits the eligibility of aliens for benefits under the subchapter of the Social Security Act that governs disability benefits. The statute provides that "[n]otwithstanding any other provision of law, no monthly benefit under this subchapter shall be payable to any alien in the United States for any month during which such alien is not lawfully present in the United States as determined by the Attorney General." 42 U.S.C. § 402(y) (emphasis added). The November 1999 letter to Taylor explained that based on the information available to the SSA, Taylor did not meet the lawful presence requirement.

Two months later, as a follow-up to the decision of the ALJ, the SSA sent a second letter to Taylor seeking further information to establish the months in which she worked during her period of disability. That letter also reminded Taylor that in order to receive benefit checks, she must furnish the SSA with documents to show that she was legally admitted to the United States.

Taylor responded in January 2000 with a legal memorandum to the SSA, arguing that the restrictions on benefits for non-qualified aliens did not apply to her. The record shows that in March 2000, the SSA explained to Taylor's attorney that no determination had been made regarding Taylor's lawful presence in the United States, and that Taylor must submit original immigration documents to demonstrate her lawful presence.

A subsequent review of Taylor's records by the SSA's Office of Disability and International Operations ("ODIO") raised concern about whether she had engaged in substantial gainful activity since the onset of her disability (which would render her ineligible for benefits, 20 C.F.R. § 404.1520(b)), so on September 22, 2000, ODIO requested that the SSA Appeals Council review the decision. The SSA sent Taylor another letter explaining that it was suspending benefits pending further investigation of her earnings for 1997 through 1999 and proof of her citizenship or lawful presence. The Appeals Council reopened the decision with respect to whether Taylor had engaged in any substantial gainful activity from 1997 through 1999, and remanded Taylor's case to a different ALJ for consideration of that question.

ALJ James Stubbs sent Taylor a letter explaining the issues to be considered at the second hearing. These issues did not include the question of Taylor's lawful presence in the United States. The ALJ invited Taylor to submit a written response if she objected to the statement of issues. In response, Taylor submitted a memorandum arguing that the restrictions on payments to non-qualified aliens did not apply to her.

After a hearing to determine whether Taylor had engaged in substantial gainful activity since the onset of her disability, the ALJ found that Taylor was disabled as alleged, but engaged in substantial gainful activity for four months after the onset of her disability. The ALJ did not make any findings on her lawful presence in the United States.

Taylor then petitioned the district court in March 2003 for a writ of mandamus compelling the Commissioner of Social Security to pay past-due benefits. The district court granted the Commissioner's motion to dismiss, finding that the SSA acted in accordance with its procedures, that the decision of the ALJ did not entitle Taylor to benefits because immigration requirements were not decidedly within the purview of the ALJ, and that Taylor failed to show that she was lawfully residing in the United States.

II.

The district courts have original jurisdiction over any mandamus action "to compel an officer or employee of the United States or any agency thereof to perform a duty owed to the plaintiff." 28 U.S.C. § 1361. "[T]he writ of mandamus is intended to provide a remedy for a plaintiff only if he has exhausted all other avenues of relief and only if the defendant owes him a clear nondiscretionary duty." Hatcher v. Heckler, 772 F.2d 427, 432 (8th Cir. 1985). Stated differently, "[a] party seeking issuance of a writ of mandamus must `have no other adequate means to attain the relief he desires and [must show that his] right to issuance of the writ is clear and undisputable.'" In re Mo. Dep't of Natural Res., 105 F.3d 434, 436 (8th Cir. 1997) (alteration in original) (quoting Allied Chem. Corp. v. Daiflon, Inc., 449 U.S. 33, 35, 101 S.Ct. 188, 66 L.Ed.2d 193 (1980) (per curiam)).

Taylor argues that the SSA has a clear duty to pay her benefits under the Social Security Act. Taylor acknowledges that an alien who is not a "qualified alien" within the meaning of 8 U.S.C. § 1641 generally is ineligible to receive any federal public benefits. 8 U.S.C. § 1611(a). Taylor observes, however, that this general rule "shall not apply . . . to any benefit if nonpayment of such benefit would contravene an international agreement described in section 233 of the Social Security Act." 8 U.S.C. § 1611(b)(2). Taylor claims that the Agreement on Social Security Between the Government of the United States of America and the Government of the United Kingdom of Great Britain and Northern Ireland, Feb. 13, 1984, U.S.-U.K., T.I.A.S. No. 11,086 (the "Agreement"), entitles her to benefit payments.

Section 233 of the Social Security Act authorizes the President to enter into agreements establishing totalization arrangements between the United States social security system and the social security system of a foreign country. 42 U.S.C. § 433(a). Such an agreement is not a treaty ratified by the United States Senate, pursuant to Article II, Section 2 of the Constitution. Rather, the Act provides that such an agreement shall become effective on the date specified in the agreement, provided that the date occurs a sufficient period of time after the President transmits the agreement to the Congress, and neither House of Congress has adopted a resolution disapproving the agreement. 42 U.S.C. § 433(e)(2); but see INS v. Chadha, 462 U.S. 919, 103 S.Ct. 2764, 77 L.Ed.2d 317 (1983). The declared purpose of these agreements is to establish "entitlement to and the amount of . . . benefits based on a combination of an individual's periods of coverage under the [United States] social security system . . . and the social security system of such foreign country." 42 U.S.C. § 433(a).

In 1984, the United States entered into the Agreement on Social Security with the United Kingdom. While Taylor never worked in the United Kingdom, and thus does not require a totalization of periods of coverage under separate social security systems, the authorizing statute also provides that "[a]ny such agreement may contain other provisions which are not inconsistent with the other provisions of this subchapter and which the President deems appropriate to carry out the purposes of this section." 42 U.S.C. § 433(c)(4). Taylor contends that one such "other provision," Article 3 of the Agreement, supports her claim to benefits. Article 3 provides:

[a] person who is or has been subject to the laws of one Party and who resides within the territory of the other Party shall, together with his dependants, receive equal treatment with nationals of the other Party in the application of the laws of the other Party regarding the payment of benefits.

Taylor argues that because she was born in the United Kingdom and was subject to the laws of that country for the first ten years of her life, this provision demands equal treatment for her — that is, she should be treated as a national of the United States for purposes of Social Security benefits. She contends that because a national of the United States with her disability would be entitled to benefits, she is entitled to "equal" benefits under Article 3.

However the Agreement is interpreted and applied to Taylor's situation, we conclude that it does not afford Taylor a basis for mandamus relief. Even were the Agreement interpreted as Taylor suggests, her claim for benefits faces another hurdle. An Act of Congress passed subsequent to a treaty nullifies or supersedes the treaty to the extent that the two conflict, see Breard v. Greene, 523 U.S. 371, 376, 118 S.Ct. 1352, 140 L.Ed.2d 529 (1998) (per curiam), and that same rule applies a fortiori to an international agreement that lacks the constitutional status of a treaty. In 1996, as noted, federal law was amended to provide that no monthly disability benefit "shall be payable to any alien in the United States for any month during which such alien is not lawfully present in the United States as determined by the Attorney General." 42 U.S.C. § 402(y) (emphasis added). Thus, Taylor's eligibility for benefits ultimately turns not merely on the U.S.-U.K. Agreement, but on whether she is or has been "lawfully present in the United States" during any period of disability. We turn now to that question.

III.

The prohibition of § 402(y) on payment of benefits to an alien "not lawfully present in the United States" dovetails with a pre-existing provision of the Personal Responsibility and Work Opportunity Reconciliation Act of 1996, 8 U.S.C. § 1611(b)(2). This statute establishes that the general prohibition on payment of federal public benefits to an alien who is not "a qualified alien" does not apply to disability benefits for "an alien who is lawfully present in the United States as determined by the Attorney General." Id. The federal regulations that implement the Personal Responsibility and Work Opportunity Reconciliation Act of 1996 explain that:

For the purposes of section 401(b)(2) of Pub.L. 104-193 only, "an alien who is lawfully present in the United States" means: . . . (2) an alien who has been inspected and admitted to the United States and who has not violated the terms of the status under which he or she was admitted or to which he or she has changed after admission.

8 C.F.R. § 103.12(a)(2) (emphasis added).

This definition of an alien "lawfully present in the United States" provides a potential avenue of relief for Taylor. Taylor was inspected and admitted to the United States in 1984 as an immediate relative of a citizen of the United States. See 8 U.S.C. § 1151(b). The district court thought that her adoptive father's petition for immediate relative status was automatically revoked when Taylor reached age 21, pursuant to 8 C.F.R. § 205.1(a)(3)(i)(F), but the record does not appear to support that conclusion. The automatic revocation occurs only if the alien reaches age 21 before commencing her journey to the United States (which Taylor did not) or if the alien reaches age 21 before a decision on a pending application for adjustment of status becomes final (and there is no evidence in the record that Taylor ever applied for adjustment of status). See 8 C.F.R. § 205.1(a)(3). Thus, it is possible that the petition for immediate relative status was not revoked when Taylor reached age 21, but rather — if the 1984 visa petition was "currently valid" as of her 21st birthday — automatically converted to an approved petition for classification as an unmarried daughter of a citizen of the United States, pursuant to 8 C.F.R. § 204.2(i)(2). See 8 U.S.C. § 1153(a)(1). In that case, Taylor may have been legally present throughout her time in the United States.

While this possibility ultimately may provide Taylor with a basis for relief, she has not raised this precise argument in the administrative process or in this litigation, and we conclude for two principal reasons that it is insufficient at this time to justify a writ of mandamus. First, Taylor has not exhausted all other avenues that could secure the requested relief. The record shows that the SSA has never reached a final determination concerning Taylor's lawful presence in the United States. The SSA informed Taylor that she must produce original immigration documents to establish her lawful presence. After Taylor submitted photocopies of documents, an SSA representative explained the requirement of original documents to Taylor's attorney on March 7, 2000. But because Taylor apparently never furnished original immigration documents, the SSA never reached a final determination on the crucial issue of lawful presence.

The Program Operations Manual System, the SSA's internal procedural guidelines, explain that in order to receive benefits:

[A]n individual who is not a United States Citizen or a U.S. national and is present in the U.S. must have authorization from INS to lawfully remain in the U.S. SSA accepts evidence of alien status, in support of a claim for benefits, based on established legal principles governing the rules of evidence. Only original, unexpired documents are acceptable.

POMS GN 00303.400(A) (emphasis added). The POMS provisions regarding "Developing Lawful Presence of an Alien in the U.S." state that "[t]he claimant must submit an original document or a copy certified by the issuing agency," and that "[a] copy of a [Department of Homeland Security] document (rather than an original) is not acceptable evidence of U.S. lawful presence." POMS RS 00204.020(C)(1). These directives reflect the SSA's efforts to prevent document fraud, and to implement the requirement of 42 U.S.C. § 402(y) that only persons lawfully present in the United States are eligible for benefits. Under SSA procedures, the agency cannot process an application without original immigration documents, and when immigration documents appear to be genuine, the agency must verify the alien's immigration status with the Department of Homeland Security (DHS). See POMS RS 00204.020(C); POMS RM 00203.720(B). Consistent with section 402(y), which provides that the Secretary of Homeland Security (formerly the Attorney General) determines whether an alien is lawfully present, SSA procedures provide that the DHS ultimately adjudicates lawful presence upon a referral from the Social Security Administration. Id.; see also POMS RM 00203.735.

We have said that "the POMS are entitled to respect as publicly available operating instructions for processing Social Security claims," Reutter ex rel. Reutter v. Barnhart, 372 F.3d 946, 951 (8th Cir. 2004) (internal quotation omitted), and we see no reason why the SSA is not entitled to require original documentation before making a determination on lawful presence in Taylor's case. If Taylor expeditiously provides the necessary original documents to the SSA, then we expect that the SSA should promptly obtain a determination from the DHS on her immigration status, including whether her adoptive father's initial visa petition from 1984, together with the automatic conversion provision of 8 C.F.R. § 204.2(i)(2), is sufficient to establish that Taylor has been lawfully present in the United States since her entry. Because Taylor has not exhausted this possible avenue of relief, however, she has not satisfied one of the essential prerequisites for mandamus relief.

Second, we conclude that mandamus relief is not warranted at this time, because we cannot say it is clear and undisputable that Taylor is lawfully present based on her adoptive father's initial visa petition. The immigration regulations define an alien lawfully present in the United States as one "who has been inspected and admitted to the United States and who has not violated the terms of the status under which he or she was admitted." 8 C.F.R. § 103.12(a)(2) (emphasis added). As noted, the initial visa petition provided that Taylor would apply for adjustment of status to that of a lawful permanent resident, thus presumably making such application one of the "terms of the status under which . . . she was admitted." There is no evidence in the record that she ever made such an application. If she failed to do so, then it may be that she violated the terms of the status under which she was admitted, and so does not qualify as an alien "lawfully present in the United States" within the meaning of the governing regulations. If she did apply, then it is conceivable that her immediate relative status was revoked pursuant to 8 C.F.R. § 205.1(a)(3)(i)(F).

The POMS, moreover, set forth specific documentary evidence that is required by DHS to establish lawful presence in the United States (including as a lawful permanent resident), see POMS RS 00204.205, GN 00303.440, and it is not clear that Taylor can furnish this documentation. On the other hand, if there is flexibility in the regulations, then there may be good reason under the circumstances of this case for the DHS to consider finding that Taylor's 1984 visa petition and entry documents are sufficient to establish her lawful presence. The Department of Homeland Security and the Commissioner have had no opportunity to address these points in the administrative process, and given the absence of evidence regarding whether Taylor applied for adjustment of status, or the implications of a failure to do so under the immigration laws, we do not believe Taylor's right to benefits based on her adoptive father's initial petition is clear and undisputable.

The judgment of the district court is affirmed.