This case vividly illustrates the labyrinthine character of modern immigration law- — a maze of hyper-technical statutes and regulations that engender waste, delay, and confusion for the Government and petitioners alike. The inscrutability of the current immigration law system, and the interplay of the numerous amendments and alterations to that system by Congress during the pendency of this case, have spawned years of litigation, generated two separate opinions by the District Court, *100and consumed significant resources of this Court. With regret and astonishment, we determine, as explained more fully below, that this case still cannot be decided definitively but must be remanded to the District Court, and then to the Board of Immigration Appeals (“BIA”), for further proceedings.
The Government appeals from a judgment of the United States District Court for the Eastern District of New York (Jack B. Weinstein, Judge) granting a writ of habeas corpus to petitioner, David Anthony Drax, who was ordered deported by an Immigration Judge on the basis of a drug conviction and a conviction for attempted weapons possession. We disagree with the reasoning of the District Court and grant the writ on alternative grounds. However, we take this opportunity to commend the District Court’s heroic efforts. We are mindful that district courts are severely constrained in the time and resources they can allocate to any one case and that it is frequently the case that only a Court of Appeals, at its relative leisure, can devote the excessive time required to penetrate in part this dark thicket of the law.
The principal questions presented on appeal are: (i) whether the Immigration and Nationality Technical Corrections Act of 1994 (“INTCA”) § 203(c), Pub.L. No. 103-416, 108 Stat. 4305, 4311 (Oct. 25, 1994), codified at 8 U.S.C. §§ 1182, 1251 (1994), operates retroactively to foreclose discretionary relief from deportation under Immigration and Nationality Act (“INA”) § 212(c), 8 U.S.C. § 1182(c) (1994), to aliens who, like the petitioner, pleaded guilty to attempted weapons offenses prior to the passage of the INTCA; and (ii) whether the Immigration Judge at the petitioner’s immigration hearing erred by informing the petitioner that no relief was available, precluding him from applying for a combination of relief from deportation and adjustment of status known as “Ga-bryelsky relief.”
On the first issue, the District Court held that INA § 212(c). relief from deportation remains available to the petitioner because the INTCA does not operate retroactively to render attempted weapons convictions deportable offenses for which no § 212(c) relief is available. We hold that the District Court’s grant of a writ of habeas corpus on this ground was error because § 203(c) of the INTCA does operate retroactively to make attempted weapons convictions deportable offenses and to foreclose § 212(c) relief from deportation for petitioners like Drax who pleaded guilty to such offenses prior to the passage of the INTCA.
On the second issue, the District Court held that because the petitioner’s chance of success under the Gabryelsky process was too attenuated, the Immigration Judge did not err in failing to recognize that Ga-bryelsky relief was possible. We hold that the petitioner had a reasonable likelihood of success under the Gabryelsky process and that, in the circumstances here presented, the Immigration Judge erred by failing to recognize the availability of such relief.
Accordingly, we affirm on alternative grounds the judgment of the District Court granting the writ of habeas corpus. We remand to the District Court with instructions to remand the cause to the BIA to allow the petitioner to pursue Ga-bryelsky relief.
BACKGKOUND
The facts relevant to this appeal are set forth below, as well as in the District Court’s opinion in Drax v. Reno, 2001 WL *1011180678, No. 99 CV 3613 (E.D.N.Y. Oct. 3, 2001) (“Drax I”),1 and its superseding opinion in Drax v. Ashcroft, 178 F.Supp.2d 296 (E.D.N.Y.2001) (“Drax II”).
I. Drax’s Convictions
Drax, a citizen of Trinidad and Tobago, entered the United States twenty-seven years ago, at age fifteen. He obtained lawful permanent resident status in 1984 at age twenty-three. He was married to a lawful permanent resident from 1981 until her death in 1994, and he married a United States citizen in April 2000. His father and siblings are naturalized United States citizens.
Drax pleaded guilty in New York State Supreme Court, Kings County, on May 26, 1993, to attempted criminal possession of a firearm in the second degree, a class C felony. He also pleaded guilty in that Court on April 12, 1996, to sale of a controlled substance in the fifth degree, a class D felony. Drax was sentenced simultaneously in April 1996 to concurrent terms of incarceration of one-to-three years for the weapons charge and two-to-four years for the drug charge.
II. Statutory Overview
At the time of Drax’s drug and attempted weapons convictions, he was eligible for discretionary relief from deportation for his drug offense pursuant to INA § 212(c) (“ § 212(c)”).2 No such relief was required for his attempted weapons conviction because that offense was not a deportable crime under INA § 241(a), 8 U.S.C. § 1251(a)(2)(C) (1988). See Discussion, section II.A, post.
In 1994, however, Congress enacted the INTCA, which made numerous changes to the INA including, in INTCA § 203, changes that made attempted weapons possession a deportable crime for which no § 212(c) relief is available. INTCA § 203, 108 Stat. at 4311; see Discussion, section II.B, post. Accordingly, assuming that the INTCA applies retroactively — a conclusion we reach below — Drax’s attempted weapons conviction is a deportable offense for which § 212(c) relief from deportation is not available.
For his attempted weapons conviction, Drax may nonetheless apply for a form of relief called “adjustment of status,” in which a deportable alien’s status is adjusted, pursuant to INA § 245(a) (“§ 245(a)”), 8 U.S.C. § 1255(a), to the status of admissible alien seeking to enter the country.3 *102See United States v. Gonzalez-Roque, 301 F.3d 39, 42 n. 1 (2d Cir.2002) (describing “adjustment of status”); Matter of Rainford, 20 I. & N. Dec. 598, 601 (B.I.A.1992) (same).
Adjustment of status, however, is not available for Drax’s drug conviction. See Jenkins v. INS, 32 F.3d 11, 15 (2d Cir. 1994) (holding that an alien with a drug conviction is “barred from adjusting his status to that of a lawful permanent resident under § 245(a) ... because his drug conviction renders him inadmissible to the United States pursuant to 8 U.S.C. § 1182(a)(2)(A)(i)(II)”), overruled on other grounds, Aguirre v. INS, 79 F.3d 315 (2d Cir.1996).
In INS v. St. Cyr, 533 U.S. 289, 121 S.Ct. 2271, 150 L.Ed.2d 347 (2001), the Supreme Court, affirming this Court’s decision in the same case, 229 F.3d 406 (2d Cir.2000), held that certain 1996 changes to the immigration laws that would significantly alter the above analysis do not apply retroactively to petitioners such as Drax who pleaded guilty prior to the effective date of the changes. See St. Cyr, 533 U.S. at 326, 121 S.Ct. 2271 (affirming St. Cyr, 229 F.3d at 421). In particular, the Supreme Court held that Congress’s April 24,1996 enactment of § 440(d) of the Antiterrorism and Effective Death Penalty Act of 1996 (“AEDPA”), Pub.L. No. 104-132, 110 Stat. 1214, 1277 (Apr. 24, 1996), which severely curtailed the availability of § 212(c) relief, and its subsequent enactment of § 304(b) of the Illegal Immigration Reform and Immigrant Responsibility Act (“IIRIRA”), Pub.L. No. 104-208, Div. C, Title III, 110 Stat. 3009-546, 3009-597 (Sept. 30, 1996), which eliminated § 212(c) relief altogether, do not operate retroactively to bar § 212(c) relief to petitioners such as Drax. St. Cyr, 533 U.S. at 297-98, 121 S.Ct. 2271.
III. Proceedings Before the Immigration Judge and the BIA
In January 1997, the Immigration and Naturalization Service (“INS”)4 commenced deportation proceedings against Drax by Order to Show Cause. In July 1997, Drax appeared pro se before an Immigration Judge, admitted his two convictions, and was found deportable. Drax I, at 4. At this appearance, Drax asked the Immigration Judge if he was “qualified for any type of a waiver” of deportation. Id.
The Immigration Judge, ruling several years prior to our decision or the Supreme Court’s decision in St. Cyr, erroneously informed Drax that no relief from deportation was available to him under § 212(c) for his drug conviction because the restrictions in AEDPA § 440(d) applied retroactively to bar any such relief.5 He further *103informed Drax that he was ineligible for an adjustment of status under § 245(a) because adjustment of status — a form of relief from deportation available to aliens with weapons convictions — is not available to aliens with drug convictions. Ruling that Drax was ineligible for relief from deportation under § 212(c) or adjustment of status under § 245(a), the Immigration Judge ordered Drax deported.
On March 1, 1998, Drax, still acting pro se, filed an appeal with the BIA, which the BIA rejected as untimely.6 In July 1998, The Legal Aid Society of New York entered the case as counsel for petitioner and obtained permission to file a late appeal to the BIA. In that appeal, counsel for Drax argued that AEDPA § 440(d) did not apply retroactively to preclude § 212(c) relief from deportation to Drax because that provision did not apply to aliens who had pleaded guilty, prior to AEDPA, to deport-able crimes for which § 212(c) relief was available at the time of the plea.
On May 28, 1999, the BIA dismissed Drax’s appeal pursuant to the Attorney General’s opinion in Matter of Soriano, 21 I. & N. Dec. 516, 533 (Op. Att’y Gen. Feb. 21, 1997), which had held — contrary to our later holding and the Supreme Court’s later holding in St. Cyr — that AEDPA § 440(d) operates retroactively to restrict the availability of § 212(c) relief from deportation in all cases, except where an application for § 212(c) relief was filed pri- or to the enactment of the statute. In re Drax, BIA Decision, File #A38736811. The BIA therefore held that AEDPA § 440(d) operated to preclude § 212(e) relief from deportation for Drax.
IV. Habeas Corpus Proceedings in the District Court
On June 24,1999, Drax, still represented by counsel, filed a petition in the District Court for a writ of habeas corpus. In his petition, he claimed that he should be permitted to apply to an Immigration Judge for § 212(c) relief from deportation on the ground that, according to certain district court opinions foreshadowing the Supreme Court’s opinion in St. Cyr, such relief remained available to him. See, e.g., Mojica v. Reno, 970 F.Supp. 130 (E.D.N.Y.1997). In opposition, the Government asserted for the first time that, even if AEDPA § 440(d) did not apply retroactively, Drax would still be ineligible for § 212(c) relief from deportation for his attempted weapons conviction under the reasoning of Cato v. INS, 84 F.3d 597 (2d Cir.1996), discussed below in Discussion, section II.A.
Drax’s counsel responded by a letter submitted in July 1999, in which he asserted for the first time that, should Drax prevail regarding the nonretroactivity of AEDPA § 440, Drax should be permitted concurrently to seek (i) § 212(c) relief from deportation for his drug conviction, and (ii) § 245(a) adjustment of status for his weapons conviction. Under the holding of Matter of Gabryelsky, 20 I. & N. Dec. 750 (B.I.A.1993), the fact (i) that § 212(c) relief from deportation was unavailable because of the weapons conviction, and (ii) that § 245(a) adjustment of status was unavailable because of the drug conviction, would both be remedied by the legal fiction that § 212(c) relief and § 245(a) adjustment of status take place at exactly the same time, thereby negating each ineligibility as an obstacle to the other proceeding. See Drax II, 178 F.Supp.2d at 304.
*104On October 3, 2001, the District Court granted Drax’s petition for a writ of habe-as corpus, holding that Drax should be permitted to pursue Gabryelsky relief— that is, he should be permitted to apply for simultaneous relief under § 212(c) and § 245(a). The District Court first concluded that Drax had properly exhausted his administrative remedies, as then required by INA § 106(c), 8 U.S.C. § 1105a(c) (1994), repealed by IIRIRA § 306(b), 110 Stat. at 3009-612.7 Although Drax had not specifically requested Gabryelsky relief from the Immigration Judge or the BIA, the District Court deemed his pro se requests for “any kind” of relief and for “any type of a waiver,” and the Immigration Judge’s denial that any relief was available, to be sufficient for exhaustion. Drax I, at 19-20.
On the merits, the District Court concluded that Drax remained eligible to apply for § 212(c) relief from deportation for his drug conviction under St. Cyr, because he had pleaded guilty to his offenses prior to the enactment of AEDPA. Drax I, at 20 (citing St. Cyr, 533 U.S. at 326, 121 S.Ct. 2271). With respect to Drax’s weapons conviction, the District Court concluded that Drax was eligible to apply for § 245(a) adjustment of status because his father’s filing of an 1-130 petition in October 1998 had caused a visa to be “immediately available” before the BIA denied Drax’s appeal in May 1999.8 Drax I, at 23. The District Court held that because Drax had demonstrated that he met the separate eligibility requirements for § 212(c) relief from deportation for his drug convietion and § 245(a) adjustment of status for his attempted weapons conviction, he was entitled to a new immigration hearing at which he could request Gabryelsky relief— i.e, apply for both forms of relief simultaneously. Id.
On October 18, 2001, the Government filed a motion pursuant to Federal Rule of Civil Procedure 59(e) requesting that the District Court alter or amend its October 3, 2001 judgment. The Government argued principally that the District Court had misunderstood the application process for adjustment of status pursuant to § 245(a), and that, under the actual process, Drax had neither made a proper application for adjustment of status nor had a visa “immediately available” at the relevant time, as required by statute.
On November 14, 2001, the District Court issued a second opinion, Drax II, 178 F.Supp.2d 296 (E.D.N.Y.2001), in which it adopted the Government’s arguments. The District Court held that Drax did not qualify for Gabryelsky relief because he “[did] not meet the requirement of an immediately available visa.” Id. at 298-99. The Court further concluded that no visa ever was “immediately available” to Drax at any relevant time, and that any prospect of eligibility for Gabryelsky relief in the future was “too attenuated.” Id. at 306-07. Because Drax failed to meet the independent requirements of § 245(a), the District Court held, he could not qualify for Gabryelsky relief. Id.
However, the District Court granted a writ of habeas corpus on different grounds by sua sponte identifying a new argument favorable to Drax — that Drax’s attempted *105weapons conviction did not render him de-portable and, therefore, Drax could seek relief from deportation solely by applying for § 212(c) relief from deportation for his drug conviction.9 Id. at 307. The District Court held that Drax’s attempted weapons conviction was not a deportable offense because he had pleaded guilty to the offense one year before the 1994 enactment of INTCA § 203, which for the first time included attempted weapons crimes in the category of weapons crimes for which an alien could be deported under INA § 241 (“§ 241”), 8 U.S.C. § 1251(a)(2)(C) (1994).10 Drax II, 178 F.Supp.2d at 307-OS. The District Court held that § 203 of the INTCA did not render Drax’s attempted weapons conviction a deportable offense because § 203(c) did not unambiguously evidence Congress’s intent that it operate retroactively. Id. at 307-08. The District Court gave particular weight to the word “technical” in the Act’s title — the Immigration and Nationality Technical Corrections Act — reasoning that “[t]he Act’s innocuous title raises a doubt that ‘Congress itself has affirmatively considered the potential unfairness of retroactive application’ of the new law.” Id. at 308 (quoting St. Cyr, 533 U.S. at 316, 121 S.Ct. 2271).
A new judgment granting Drax’s petition for a writ of habeas corpus was entered on November 14, 2001. Drax II, 178 F.Supp.2d at 296.
V. Claims on Appeal
The Government timely appealed the District Court’s judgment entered on the basis of Drax II, arguing that the District Court erred in holding that INTCA § 203(c) does not apply retroactively to convictions entered prior to its enactment. The Government further argued that the District Court was not empowered to consider such a retroactivity argument because Drax had not exhausted the claim in INS proceedings.
Drax did not cross-appeal the District Court’s denial of his claim for Gabryelsky relief. He did, however, renew his argument that he is eligible for Gabryelsky relief in his opposition to the Government’s arguments. We hold that Drax’s renewal of his Gabryelsky claim in his appellate brief is sufficient for us to consider the claim. An “appellee may, without taking a cross-appeal, urge in support of a decree any matter appearing in the record, although his argument may involve an attack upon the reasoning of the lower court or an insistence upon matter overlooked or ignored by it.” International Ore & Fertilizer Corp. v. SGS Control Servs., Inc., 38 F.3d 1279, 1285 (2d Cir. 1994) (citation and internal quotation *106marks omitted).11 Appellee in this case does not seek to “enlarg[e] his own rights,” under the appeal, but seeks merely “to sustain a judgment on ... grounds with support in the record,” id. — grounds that were the basis of District Court’s opinion granting relief in Drax I, which was later rescinded upon reconsideration in Drax II. See Arlinghaus v. Ritenour, 622 F.2d 629, 638 (2d Cir.1980) (“[T]he judgment of a lower court may be affirmed without cross-appeal on the basis of any argument that is supported by the record, whether it was ignored by the court below or flatly rejected.” (citation and internal quotation marks omitted)). Drax’s claim is not an impermissible claim for “supplement[al]” relief, see Beharry v. Ashcroft, 329 F.3d 51, 63 (2d Cir.2003), but rather a claim that is inextricably intertwined with the relief ultimately granted by the District Court.12
Accordingly, on appeal we consider: (1) the Government’s argument that the District Court’s grant of relief was improper because the INTCA applies retroactively to bar § 212(c) relief to aliens with attempted weapons convictions; and (2) the petitioner’s argument that, even if the Government is correct, the District Court should have remanded to the BIA to allow him to pursue coordinated § 212(c) relief from deportation and § 245(a) adjustment of status under Gabryelsky.
discussion
I. Standard of Review
“[We] review[ ] a district court’s grant of a writ of habeas corpus de novo and the factual findings supporting the grant for clear error.” Theodoropoulos v. INS, 313 F.3d 732, 736 (2d Cir.2002).
II. The Government’s Retroactivity Claim
In Drax II, the District Court held that INTCA § 203 does not operate retroactively to make attempted weapons convictions deportable offenses for petitioners such as Drax who pleaded guilty prior to the statute’s enactment. Thus, notwithstanding what the Court perceived to be the unavailability of Gabryelsky relief, it concluded that Drax was entitled to a writ of habeas corpus to pursue § 212(c) relief because INTCA § 203 did not operate retroactively to render Drax’s weapons conviction a barrier to such relief. The Government appeals this holding.
We hold, contrary to the conclusion of the District Court, that INTCA § 203 operates retroactively to render Drax’s attempted weapons conviction a deportable offense for which § 212(c) relief is not available. Accordingly, the District Court erred in concluding that petitioner could pursue § 212(c) relief from deportation for his drug conviction independent of the Ga-*107bryelsky system because his weapons conviction served as a bar to such relief.
A. Section 212(c) relief
Prior to its partial repeal by AEDPA, and subsequent complete repeal by IIRI-RA, INA § 212(c), 8 U.S.C. § 1182(c) (1994), permitted aliens convicted of certain deportable crimes to seek relief from deportation “in the discretion of the attorney general.” See note 2, ante (full text of § 212(c)). In considering an application for § 212(c) relief, an Immigration Judge was obligated to “balance the adverse factors evidencing an alien’s undesirability as a permanent resident with the social and humane considerations presented in his behalf to determine whether the granting of section 212(c) relief appears in the best interests of this country.” United States v. Perez, 330 F.3d 97, 102 (2d Cir.2003) (citation and internal quotation marks omitted).
Former § 212(c) by its terms provided relief only from “exclusion,” and made no mention of relief from deportation. 8 U.S.C. § 1182(c) (1994) (emphasis added).13 Specifically, it provided that aliens convicted of a criminal offense rendering them excludable under § 212(a), 8 U.S.C. § 1182(a), could be granted relief from exclusion “in the discretion of the Attorney General,” provided that the alien had not been “convicted of one or more aggravated felonies” and served “for such felony or felonies a term of imprisonment of ... five [or more] years.” 8 U.S.C. § 1182(c) (1994).
In Francis v. INS, 532 F.2d 268 (2d Cir.1976), we extended § 212(c) discretionary relief, which was previously available only to aliens subject to exclusion under § 212(a), 8 U.S.C. § 1182(a), to aliens (such as Drax) who were subject to deportation under § 241(a), 8 U.S.C. § 1251(a) (1994) (current version at 8 U.S.C. § 1227(a) (2000)). Francis, 532 F.2d at 272-73; see also, e.g., St. Cyr, 229 F.3d at 410; Cato v. INS, 84 F.3d 597, 599 (2d Cir.1996). However, because § 212(c) relief from deportation arose as a judicial extension of that section’s provision for relief from exclusion, we held that in order for an alien to be eligible to apply for § 212(c) relief from deportation, an alien’s deportable offense under § 241(a) must be analogous to a ground of “exclusion” contained in INA § 212(a). See Bedoya-Valencia v. INS, 6 F.3d 891, 894 (2d Cir. 1993). Thus, a § 212(c) waiver is available in a deportation proceeding only “if the reason for deportability [under § 241(a)] is ‘substantially equivalent’ to a ground of exclusion listed in § 212(a).” Cato, 84 F.3d at 599 (quoting Bedoya-Valencia, 6 F.3d at 894 (emphasis added)).
In Bedoya-Valencia we recognized an additional category of eligibility for § 212(c) relief — relief for aliens whose ground for deportation under § 241(a) could not possibly be analogous to a ground for exclusion under § 212(a) because of the inherent differences between deportation and exclusion. See Bedoyctr-Valencia, 6 F.3d at 897 (holding that, “[a]t least with respect to entry without inspection, a ground of deportation that could not *108conceivably have such an analogue, there is no basis in statutory text or legislative purpose to preclude [this] modest extension of the Francis rule.”)- '
Thus, as we later summarized in Cato, an alien subject to deportation under § 241(a) could fall into one of only three categories in terms of the availability vel non of § 212(c) relief:
(1) The deportee’s ground of deportation [is] congruent with a ground of exclusion listed in § 212(a). Such a deportee is eligible for § 212(c) relief.
(2) The deportee’s ground of deportation [is] one that could not possibly be analogous to a ground of exclusion. Such a deportee is also eligible for § 212(c) relief.
(3) The deportee’s ground of deportation [is] one that could conceivably have an analogous ground of exclusion under § 212(a) but ... Congress has not chosen to include that ground in § 212(a). Such a deportee is not eligible for § 212(c) relief.
Cato, 84 F.3d at 600 (emphases added).
At the time of Drax’s plea on his drug charge, his conviction fell into the first category — ie., a ground of deportation that is congruent with a ground of exclusion listed in § 212(a), rendering the deportee eligible for § 212(c) relief. Accordingly, at that time, he was entitled to apply for § 212(c) relief from deportation for the drug conviction.
At the time of Drax’s plea on his attempted weapons charge, such an offense did not render him deportable under § 241(a), so there would have been no need for § 212(c) relief on the basis of that conviction. Thus, regardless of his attempted weapons conviction, Drax was eligible for § 212(c) relief from deportation for his drug conviction, and if he had received such discretionary relief, then he no longer would have been subject to deportation.
B. Retroactivity of the INTCA
In 1994, Congress enacted the INTCA, § 203 of which made changes to the above regime that affect the status of Drax’s attempted weapons conviction.14 In particular, § 203(b)(1)(A) added attempted weapons crimes to the list of deportable offenses under INA § 241(a). However, § 203(a), which modified the list of excludable offenses under INA § 212(a), did not add attempted weapons offenses to the list of excludable crimes under INA § 212(a). Under the reasoning of Cato, 84 F.3d at 599-600, § 203 thus not only made at*109tempted weapons possession a newly de-portable offense, but also rendered attempted weapons possession a deportable offense for which no § 212(c) relief was available because the crime lacked a mirroring ground of exclusion under § 212(a).15
Accordingly, if INTCA § 203 applies retroactively to petitioners such as Drax who pleaded guilty to attempted weapons offenses prior to its passage, then Drax’s attempted weapons conviction clearly precludes him from obtaining relief from deportation under § 212(c), notwithstanding his apparent eligibility for such relief on the basis of his drug conviction. We have not previously considered whether INTCA § 203’s reclassification of attempted weapons crimes as “deportable offenses” applies retroactively to deprive aliens convicted of such offenses of § 212(c) relief from deportation. We conclude, contrary to the holding of the District Court, that the clear language of retroactivity in § 203(c) renders it applicable to convictions for attempted weapons offenses entered prior to the INTCA’s effective date, thereby eliminating the availability of § 212(c) relief from deportation for aliens convicted of such crimes.
Section 203(c) of the INTCA states as follows: “The amendments made by this section shall apply to convictions occurring before, on, or after the date of the enactment of this Act.” INTCA § 203(c), 108 Stat. at 4311; see note 14, ante (full text of § 203). In Kuhali v. Reno, 266 F.3d 93 (2d Cir.2001), we considered a nearly identical claim — whether IIRIRA § 321, 110 Stat. at 3009-628, amending the offenses considered “aggravated felonfies]” under the INA and stating that the amended definition would apply to convictions “entered before, on, or after” the date of the enactment, applied to convictions entered prior to the statute’s effective date. Kuhali, 266 F.3d at 110-11. We determined that the “before, on, or after” language in IIRIRA § 321 satisfied the Supreme Court’s requirement that there be “clear congressional intent favoring [a retroactive] result.” Id. (quoting Landgraf v. USI Film Products, 511 U.S. 244, 280, 114 S.Ct. 1483, 128 L.Ed.2d 229 (1994)) (internal quotation marks omitted). We therefore held that Kuhali, whose convictions had not rendered him deportable prior to the passage of IIRIRA, was not eligible for § 212(c) relief. Id; see also United States v. Luna-Reynoso, 268 F.3d 111, 114-116 (2d Cir.2001)(noting the retroactivity of the same “before, on, or after” language of IIRIRA § 321 in the context of an aggravated-felony sentencing enhancement).16
Unlike the provision of IIRIRA at issue in Kuhali, however, the INTCA’s title— the Immigration and Nationality Technical Corrections Act — implies that the Act makes only “technical corrections.” The District Court emphasized that the word “technical” in the Act’s title could be read to indicate that Congress did not clearly intend to amend § 212(c) substantively and retroactively, thereby rendering the language contained in § 203(c) insufficiently “clear” to justify its retroactive application. *110Drax II, 178 F.Supp.2d at 307-08. However, regardless of the meanings that may be attributed to the term “technical,” the plain language of the body of § 203(c) erases any doubt about retroactivity that could possibly be inferred from the word “technical” in the title. While the title of a statute is a “tool[ ] available for the resolution of a doubt about the meaning, of a statute,” Almendarez-Torres v. United States, 523 U.S. 224, 234, 118 S.Ct. 1219, 140 L.Ed.2d 350 (1998) (internal quotation marks and citations omitted), the “title of a statute ... cannot limit the plain meaning of the text,” Pennsylvania Dep’t of Corrections v. Yeskey, 524 U.S. 206, 212, 118 S.Ct. 1952, 141 L.Ed.2d 215 (1998) (internal quotation marks and citation omitted). “For interpretive purposes, [a title] is of use only when it sheds light on some ambiguous word or phrase.” Id. (internal quotation marks, alterations, and citations omitted). The phrase “before, on, or after” contained in § 203(c) is not ambiguous; therefore, the word “technical” in the title cannot limit the plain meaning of § 203(c), and the District Court erred in relying on it for interpretive purposes.
The word “technical” failing to create any meaningful distinction between the language of retroactivity used in INTCA § 203(c), and that contained in IIRIRA § 321, the instant case is indistinguishable from Kuhali. The 1994 amendment at issue here, like the 1996 amendment considered in Kuhali, expressly states that its expansion of the offenses considered to be deportable crimes under § 241(a) applies to convictions entered “before, on, or after” the amendment’s effective date. INT-CA § 203(c), 108 Stat. at 4311; IIRIRA § 321, 110 Stat. at 3009-628. Based on the plain meaning of the language “before, on, or after,” and our interpretation of indistinguishable language in Kuhali, we conclude that § 203(c) of the INTCA retroactively renders aliens convicted of attempted weapons possession deportable, without the possibility of § 212(c) discretionary relief from deportation.
‡ ‡ ^ ‡ ‡ ‡
Because we hold that INTCA § 203 operates retroactively, Drax’s attempted weapons conviction is a deportable offense for which § 212(c) relief from deportation is not available. The District Court thus erred in allowing Drax to rely solely upon the availability of § 212(c) relief for his drug conviction to avoid deportation.17
*111III. Petitioner’s Gabryelsky Claim
We now turn to Drax’s claim that the Immigration Judge at his immigration hearing erred by holding that, pursuant to AEDPA § 440, he was not eligible for “any type of a waiver,” thereby precluding him from applying for Gabryelsky relief.
Relying on INS regulations in force,18 the BIA in Matter of Gabryelsky, 20 I. & N. Dec. 750 (B.I.A.1993), held that an alien such as Drax who:
(i) on his drug conviction, is eligible for § 212(c) relief from deportation but ineligible for § 245(a) adjustment of status; yet
(ii) on his weapons conviction, is eligible for § 245(a) adjustment of status but ineligible for § 212(c) relief from deportation,
can simultaneously apply for both forms of relief. Gabryelsky, 20 I. & N. Dec. at 756. Gabryelsky relief operates under the legal fiction that the § 212(c) and § 245(a) procedures occur at exactly the same time, thereby eliminating the obstacle to relief otherwise posed by the other conviction. See Drax II, 178 F.Supp.2d at 304.
As the District Court noted, the “[t]he Gabryelsky method has been adopted by the BIA, and endorsed by the Courts.” Drax II, 178 F.Supp.2d at 305 (citing, inter alia, Snajder v. I.N.S., 29 F.3d 1203, 1208 (7th Cir.1994); Rivera-Saavedra v. Demore, No. C00-00464CRB, 2001 WL 1006819, at *1-2 (N.D.Cal. Aug. 24, 2001); Cinquemani v. Ashcroft, No. 00-CV-1460 (RJD), 2001 WL 939664, at *5 (E.D.N.Y. Aug. 16, 2001); Calderon v. Reno, 39 F.Supp.2d 943, 946 & n. 7 (N.D.Ill.1998); In re Rodarte-Espinoza, 21 I. & N. Dec. 150, 151-52 (B.I.A.1995)); see also United States v. Gonzalez-Roque, 301 F.3d 39, 42 (2d Cir.2002) (citing Gabryelsky, without discussing “Gabryelsky relief’). We agree that the Gabryelsky process is a viable method of seeking discretionary relief from deportation in this Circuit.
Under Gabryelsky, in order to have been eligible to apply for relief before the Immigration Judge, Drax had to be simultaneously eligible to apply for both: (i) § 212(c) relief from deportation for his drug conviction;' and (ii) § 245(a) adjustment of status for his weapons conviction. We hold (i) that Drax remained eligible for § 212(c) relief for his drug conviction at the time of his initial hearing before the Immigration Judge; and (ii) that although Drax was not eligible for an adjustment of status at the time of his immigration hearing, the Immigration Judge erred in holding that Drax could under no circumstances become eligible for such relief, because such relief (as described below) was a reasonable possibility if the Immigration Judge had been willing to grant Drax a continuance.
Because the Immigration Judge erroneously indicated to Drax — based on his understanding that AEDPA § 440(d) applied retroactively — that no relief at all was available and that he had no discretion to allow Drax to seek “any type of a waiver,” Drax was deprived of the opportunity to seek a favorable exercise of discretion through the Gabryelsky process that could have prevented his deportation. We therefore grant the writ of habeas corpus *112to permit Drax the opportunity to petition an Immigration Judge simultaneously for discretionary relief under § 212(c) and § 245(a).19
A. § 212(c) relief for Drax’s drug charge
We hold that § 212(c) relief remains available for Drax’s, drug charge, notwithstanding the numerous changes to the immigration law regime that have taken place since his April 12,1996 plea.
On April 24, 1996, Congress enacted AEDPA, of which § 440(d) “expanded the category of criminal convictions that would render an alien ineligible to apply for § 212(c) relief.” St. Cyr, 229 F.3d at 411. Specifically, § 440(d) provided that § 212(c) relief could not be granted to an alien convicted of any aggravated felony (regardless of the associated prison term), almost all drug offenses, certain weapons or national security violations, or multiple crimes of moral turpitude. See AEDPA § 440(d), 110 Stat. at 1277; Drax II, 178 F.Supp.2d at 302. Shortly thereafter, on September 30, 1996, Congress enacted IIRIRA. Section 304(a) of IIRIRA, which applies to all proceedings commenced after April 1, 1997, repealed § 212(c) in its entirety, replacing it with a form of relief called “cancellation of removal.” See IIRI-RA, § 304(a), 110 Stat. at 3009-594, codified at 8 U.S.C. § 1229b(a) (2000).
If the stringent standards of AEDPA and IIRIRA were applied retroactively in this case, they would clearly bar any possibility of § 212(c) relief from deportation for the petitioner’s drug charge. However, in INS v. St. Cyr, 533 U.S. 289, 121 S.Ct. 2271, 150 L.Ed.2d 347 (2001), the Supreme Court affirmed this Court’s conclusion that the provisions of AEDPA and IIRIRA limiting and repealing § 212(c) do not apply retroactively to an alien defendant who pleaded guilty before the passage of AED-PA.20 Id. at 326, 121 S.Ct. 2271. The Court held “that § 212(c) relief remains available for aliens, like [Drax], whose convictions were obtained through plea agreements and who, notwithstanding those convictions, would have been eligible for § 212(c) relief at the time of their plea under the law then in effect.” Id.
However, the Government argued in its reply brief before the District Court that the Supreme Court’s decision in St. Cyr did not preserve Drax’s eligibility for § 212(c) relief on his drug conviction because Drax was not in fact eligible for § 212(c) relief from deportation at the time of his plea to that charge on April 12,1996. The Government asserts that Drax was ineligible for § 212(c) relief from deportation for his drug conviction because, in accordance with our holding that his 1993 weapons conviction is a deportable offense for which no § 212(c) relief is available, his attempted weapons conviction precluded such relief at the time of his plea to the drug offense.
We reject this argument for two reasons. First, it conflates the independent disadvantages that resulting from each of Drax’s two convictions. It is not the case that Drax, at the time of his plea, was ineligible to apply for § 212(c) relief from deportation for his drug conviction; rath*113er, he was eligible for such relief, but application for such relief alone would have been futile in light of his independent de-portability on the weapons offense. Second, an application for § 212(c) relief from deportation for Drax’s drug offense at the time of his plea would not have been futile as part of an application for relief under the Gabryelsky process, which offers coordinated relief from both convictions.
Thus, because the enactment of AEDPA and IIRIRA had no effect on Drax’s continued eligibility for § 212(c) relief from deportation for his drug conviction, the key factor determining whether Drax may apply for Gabryelsky relief is the availability of an adjustment of status for his attempted weapons conviction.
B. § 245(a) adjustment of status for Drax’s attempted weapons charge
1. The adjustment of status regime
“Adjustment of status” is a form of relief that allows a deportable alien who would be admissible to the United States if he were seeking to enter the country to adjust his status to that of an alien seeking entry. INA § 245(a), 8 U.S.C. § 1255(a)21 ; see Gonzalez-Roque, 301 F.3d at 42 n. 1; see also Matter of Rainford, 20 I. & N. Dec. 598, 601 (B.I.A.1992) (“[A]n adjustment of status is merely a procedural mechanism by which an alien [already within the United States] is assimilated to the position of one seeking to enter the United States.”). Like § 212(c) relief from deportation, an adjustment of status under § 245(a) is entirely discretionary. Thus, even where an alien satisfies the statutory requirements of eligibility for an adjustment of status (discussed below), “the [INS] has discretion under section 245 to deny the application.” Jain v. INS, 612 F.2d 683, 687 (2d Cir.1979); see also INS v. Bagamasbad, 429 U.S. 24, 26-27, 97 S.Ct. 200, 50 L.Ed.2d 190 (1976) (holding that the INS need not examine an alien’s statutory eligibility for adjustment of status where the INS exercises its discretion to deny such relief).
It is clear (i) that Drax is not eligible for an adjustment of status under § 245(a) on the basis of his drug conviction because an alien with a drug conviction is not considered to be “admissible,” see Jenkins v. INS, 32 F.3d 11, 15 (2d Cir.1994), overruled on other grounds, Aguirre v. INS, 79 F.3d 315 (2d Cir.1996), but (ii) that Drax could be eligible for an adjustment of status on the basis of his weapons conviction alone because a weapons conviction “will not preclude a showing of admissibility for purposes of section 245(a),” Rainford, 20 I. & N. Dec. at 602. Therefore, if we find that Drax is eligible for adjustment of status based on his weapons conviction, then that eligibility, combined with his eligibility for § 212(c) relief from deportation for his drug conviction, would entitle him to pursue Gabryelsky relief. Accordingly, we must examine in detail the complex requirements of the § 245(a) process to determine whether an adjustment of status is available to Drax with respect to his weapons offense.
The text of § 245(a) states that an adjustment of status is available to an alien only if: “(1) the alien makes an application for such adjustment, (2) the alien is eligible to receive an immigrant visa and is admissible to the United States for permanent residence, and (3) an immigrant visa is immediately available to him at the time his application is filed.” 8 U.S.C. § 1255(a); see note 3, ante (full text of statute). Drax meets the second requirement because, as noted above, Drax is admissible to the United States and eligible to receive an immigrant visa despite *114his weapons conviction, and he may-through the Gabryelsky process — apply for § 212(c) relief from deportation to eliminate the adverse impact of his drug conviction.
Compliance with the statute’s first and third requirements requires an alien to undertake a two-step process. First, either the alien or a family relative must file a petition for an immigrant visa, so that at some point in the future such a visa may become “immediately available” to the alien. 8 U.S.C. §§ 1154, 1255(a). Second, the alien must file an 1-485 application for adjustment of status when such an immigrant visa becomes “immediately available.” 8 U.S.C. § 1255(a); 8 C.F.R. § 299.1.
An alien who, like Drax (the then-unmarried son of a United States citizen), seeks to obtain an immigrant visa on the basis of a familial relationship must cause the relevant family member to file an I-130 visa petition, or “Petition for Alien Relative,” on his behalf. INA § 203(a)(1), 8 U.S.C. §§ 1153(a)(1); INA § 204(a)(l)(A)(i), 8 U.S.C. § 1154(a)(l)(A)(i); 8 C.F.R. § 204.1(a)(1). After the relative has filed the 1-130 petition, the INS will “approve” the petition after verifying that the claimed familial relationship is bona fide. An approved petition carries with it both a “preference category” and a “priority date.” The “preference category” corresponds to the familial relationship between the alien and the person filing the 1-130 form. See INA § 203, 8 U.S.C. § 1183; 8 C.F.R. § 204.2.22 The priority date is the date on which the approved 1-130 petition was filed. 8 C.F.R. § 204.1(c); 8 C.F.R. § 245.1(g)(2). Subject to a limited exception,23 an “alien beneficiary may file the [1-485] adjustment application only after the [INS] has approved the [1-130] visa petition.” 8 C.F.R. § 245.2(a)(2)(i)(B) (emphasis added).
The processing time for approval of an 1-130 petition varies depending on whether an alien is involved in deportation proceedings. For aliens subject to deportation proceedings, the Government informs us that 1-130 petitions are frequently processed in an expedited manner that takes between sixty days and six months, although processing sometimes takes longer. MacPherson Aff. of 6/12/03 ¶ 5. For aliens not subject to deportation proceedings, the Government informs us that processing of 1-130 petitions currently takes between eight and fifty-two months. Laramie Aff. of 6/18/03 ¶ 4. When the INS approves an 1-130 petition, the petition is forwarded to the National Visa Center for further processing, and a notice of approval is sent to the alien.
Once an alien’s 1-130 petition has been approved by the INS, an alien must still wait until a visa is “immediately available” in order to file his 1-485 application. 8 U.S.C. § 1255(a); see 8 C.F.R. § 245.1(g)(1) (“An alien is ineligible for the benefits of section 245 of the Act unless an immigrant visa is immediately available to *115him or her at the time the application is filed.” (emphasis added)); 8 C.F.R. § 245.2(a)(2)(i)(A). Whether a visa is “immediately available” depends on the alien’s priority date and the length of the waiting period for a visa in the alien’s “preference category,” as indicated in the Department of State Bureau of Consular Affairs Visa Bulletin at the time the 1-485 application is filed. See 8 C.F.R. § 245.1(g)(1); see also Rainford, 20 I. & N. Dec. at 599. According to the applicable regulation, “[a]n immigrant visa is considered available for [the purpose of] accepting and processing the application Form 1-485 i[f] the preference category applicant has a priority date on the waiting list which is earlier than the date shown in the Bulletin (or the Bulletin shows that numbers for visa applicants in his or her category are current).” 8 C.F.R. § 245.1(g)(1) (emphases added).24
To illustrate the intricate provisions for adjustment of status more concretely, we consider Drax’s situation.
2. Drax’s eligibility for adjustment of status
In Drax I, the District Court erroneously relied solely upon Drax’s father’s filing of an 1-130 petition in October 1998 to conclude that Drax had a visa “immediately available,” and was thus immediately eligible for an adjustment of status and, hence, Gabryelsky relief. Drax I, at 17-19, 20-23. The Court mistakenly believed (i) that the filing of an 1-130 petition was sufficient to constitute “an application for adjustment,” as required by § 245(a), and (ii) that a visa was “immediately available” at the time the 1998 petition was filed because the January 1996 visa bulletin (which appears to be the most recent visa bulletin the Court had available) showed that there was no waiting-list for a visa in Drax’s preference category. Id. at 17-18.
After the Government filed its Rule 59(e) motion, the District Court in Drax II reconsidered its ruling and concluded that “a visa was not available to petitioner at any time before his case was closed” and that the Immigration Judge’s statement “ ‘you are not eligible for any kind of relief was not a misstatement given that Mr. Drax was not prima facie eligible for [adjustment of status or] Gabryelsky relief’ at that time. Drax II, 178 F.Supp.2d at 307. The Court rejected Drax’s argument that the Immigration Judge could have granted him a continuance to pursue an adjustment of status because it found the argument to be “a rather remote possibility” that was “too attenuated for it to be the basis for a successful habeas corpus petition.” Id.
We agree with the District Court’s determination that Drax was not at any relevant time eligible for an adjustment of status or Gabryelsky relief. Drax’s father first filed an 1-130 petition in October 1998. The record is unclear as to whether that petition was ever approved, but assuming, arguendo, that it was approved in a relatively short period of time ie.g., two to six months), at no point during the course of his deportation proceedings did a visa ever become “immediately available.” An examination of the relevant visa bulletins shows that a visa was not available until February 2000 for any first-preference 1-130 petition with a priority date of October 1998. See U.S.' Dep’t of State, *116Bureau of Consular Affairs, Visa Bulletin, Jan. 2000; id. Feb. 2000. Because Drax’s appeal to the BIA was denied in May 1999, he did not have an “immediately available” visa on the basis of his father’s 1-130 petition at any time during the pendency of his deportation proceedings. Nor was a visa immediately available to Drax on the basis of his wife’s 1-130 petition because it was not filed until May 2000, which also post-dated the BIA’s rejection of his appeal.
3. Drax’s potential eligibility for adjustment of status
We cannot, however, agree with the District Court’s conclusion that the Immigration Judge’s error of law was harmless because the possibility of Gabryelsky relief in the near future was “too attenuated for it to be the basis for a successful habeas corpus petition.” Drax II, 178 F.Supp.2d at 307. We believe that Gabryelsky relief was a reasonable possibility if the Immigration Judge had recognized that § 212(c) relief from deportation for petitioner’s drug charge remained available, and had granted Drax a continuance to pursue relief.
At petitioner’s immigration hearing on July 2, 1997, Drax (then proceeding pro se) asked, “[A]m I qualified for any type of a waiver?” After reviewing Drax’s file and noting that he was the son of a naturalized American citizen and had been convicted of both a drug offense and a weapons offense, the Immigration Judge stated as follows during a colloquy with the petitioner:
IJ: I told you there is no relief available for you. And, I want you to understand one simple thing about that. That means when the, when the Congress says that a person is convicted of selling drugs can’t stay there. It means the Judge’s discretion or his decision making powers is taken away from him. I don’t have any discretion in your ease. That’s why I’m not listening and considering all those things that you told me already. I did listen, you know I listened. I heard you. I heard every word of it. But, I can’t consider it to help you because you are legally barred by the laws of the Congress from staying here in this country.
IJ: Okay. I’m going to — as I said, there is no relief available to you. I’m going to outline every one of them for you that I know of.
IJ: You’re not eligible for a 212(c) because it’s been taken away. You have an aggravated felony drug sale. You’re not eligible for an adjustment of status. You never were eligible for an adjustment of status because adjustment will not waive a drug offense. And, it never did. So you’re not eligible for that....
Tr. of 7/2/97 at 18-19.
As discussed in the preceding sections, the Immigration Judge’s conclusion was incorrect because, contrary to what he believed, § 212(c) relief had not been eliminated by AEDPA or IIRIRA with respect to petitioner’s drug charge. Instead, the Supreme Court’s decision in St Cyr made clear that such relief remained available to petitioners such as Drax, who pleaded guilty prior to the enactment of AEDPA to crimes for which § 212(c) relief was then available. St Cyr, 533 U.S. at 326, 121 S.Ct. 2271. With § 212(c) relief from deportation available for Drax’s drug charge, and an adjustment of status under § 245(a) potentially available for his weapons conviction, Gabryelsky relief was indeed a possibility at that time. However, two separate times the Immigration Judge, no doubt acting in good faith, emphasized to the petitioner that he had no *117discretion, and that Congress had tied his hands, though in fact such discretion existed.
With the benefit of a favorable exercise of the Immigration Judge’s discretion, Drax could indeed have become eligible for an adjustment of status and Gabryelsky relief. To allow Drax to pursue an adjustment of status, the Immigration Judge could have (i) informed Drax of the availability of an adjustment of status, (ii) instructed Drax to have a relative file an I-130 form on his behalf, and (iii) granted a continuance for a reasonable amount of time to enable Drax to obtain a visa. Had the Immigration Judge given Drax such instructions at his July 2, 1997 hearing, and if Drax’s father had thereupon promptly filed an 1-130 petition, the petition would have had a priority date in July 1997. Assuming that it would have taken the INS less than 15 months to approve the petition (a realistic assumption, see Discussion, section III.B.l, ante), an immigrant visa would have become “immediately available” to Drax in October of 1998. See U.S. Dep’t of State, Bureau of Consular Affairs, Visa Bulletin, Oct. 1998. Therefore, had the Immigration Judge been willing to grant a continuance of 15 months, Drax would have become eligible for an adjustment of status, and hence Gabryelsky relief, during the course of his immigration hearing.25
Furthermore, even if the Immigration Judge had recognized the nonretroactivity of AEDPA § 440(d) and the potential availability of Gabryelsky relief but, in the exercise of his discretion, declined to grant him a continuance to pursue such relief, Drax still might have secured relief. If Drax’s father had filed an 1-130 petition in July 1997, at the same time that Drax was ordered deported, Drax would have had a visa “immediately available” to him in October 1998, see Visa Bulletin, Oct. 1998, allowing him to file an 1-485 application at that time. An 1-485 application filed at any time prior to the BIA’s rejection of his appeal in May 1999 would likely have been considered timely under the § 254(a) regime. See Gonzalez-Roque, 301 F.3d at 48-49 (noting that “[petitioner] could have requested that the BIA consider the [I-130] petition in determining whether he was eligible for an adjustment of status,” which suggests that an 1-485 application filed before the BIA would be timely). Although it seems doubtful that an 1-485 petition filed after the BIA has rendered a *118final decision would be timely,26 the fate of an 1-485 petition filed after an immigration hearing, but before a final BIA determination, is at the very least an open question. See Drax I, at 22 (discussing the absence of clear authority on this question). It suffices to note that, even without a continuance from the Immigration Judge, Drax might have succeeded in petitioning for relief from deportation if the Immigration Judge had merely recognized that Gabryelsky relief was a possiblity.
It is clear in this case that the Immigration Judge had the discretion to craft relief that would have prevented Drax from being deported. However, because of an error of law, the Immigration Judge believed that he lacked such discretion, and Drax was thus precluded from seeking Gabryelsky relief. We have frequently held in the sentencing context that a failure to exercise discretion, where a judge mistakenly believes that he lacks the authority to exercise discretion, warrants a remand for resentencing. See, e.g., United States v. Ventrilla, 233 F.3d 166, 169 (2d Cir.2000); United States v. Thorpe, 191 F.3d 339, 342-43 (2d Cir.1999) (collecting cases); see also St. Cyr, 533 U.S. at 308, 121 S.Ct. 2271 (holding that it is historically appropriate, on habeas review, to correct a failure to exercise discretion, even where it is not clear that such discretion would have been exercised favorably). We hold that the Immigration Judge’s failure to exercise his discretion in the mistaken belief that he lacked the authority to do so was prejudicial error.27
The Immigration Judge’s error of law with respect to the retroactivity of AED-PA § 440(d), and his consequent failure to exercise his discretion to determine whether to facilitate such relief, warrant the reopening of Drax’s deportation proceedings. Accordingly, we affirm the District Court’s grant of a writ of habeas corpus to permit Drax to pursue Gabryelsky relief before an Immigration Judge. As both § 212(c) relief from deportation and § 245(a) adjustment of status are discretionary, the Immigration Judge will need to determine whether petitioner’s case merits a favorable exercise of the Judge’s discretion.
C. Remedy
We instruct the BIA on remand to permit the petitioner to pursue Gabryelsky relief by allowing Drax to make a renewed application to adjust his status pursuant to § 245(a). To the extent that Drax may benefit from any changes in his circumstances since his appearance before the Immigration Judge in 1997 (such as his marriage to a United States citizen in April 2000, and his having obtained an approved 1-130 petition on the basis of that relationship28), the BIA is instructed *119to give Drax the benefit of those changed circumstances. Furthermore, to the extent that Drax is prejudiced by having to begin the adjustment-of-status process now — rather than starting immediately following his hearing before the Immigration Judge in July 1997, as he presumably would have done if the Immigration Judge had not erroneously informed him that no relief was available — the BIA is instructed to fashion such relief as may be appropriate to return him to the position in which he would have been absent the Immigration Judge’s error.
CONCLUSION
For the reasons stated above, and with an appreciation of the extraordinary effort invested in this case by both the Immigration Judge and the District Court, the judgment of the District Court granting Drax’s petition for a writ of habeas corpus is AffiRmed, as modified (i) to preclude § 212(c) relief from deportation outside of the Gabryelsky process because such relief is foreclosed by retroactive application of INTCA § 203, and (ii) to permit the petitioner to pursue Gabryelsky relief before an Immigration Judge. The cause is remanded to the District Court, with instructions to remand to the BIA. In light of the extended prolongation of the administrative and judicial proceedings in this case, we direct the BIA and IJ to give expedited consideration to this matter.
. The text of the superseded opinion was withdrawn and is no longer available online. See Drax I, 2001 WL 1180678. Accordingly, all page citations to Drax I refer to the docketed slip opinion.
. Section 212(c) provided in full:
Aliens lawfully admitted for permanent residence who temporarily proceeded abroad voluntarily and not under an order of deportation, and who are returning to a lawful unrelinquished domicile of seven consecutive years, may be admitted in the discretion of the Attorney General without regard to the provisions of subsection (a) of this section (other than paragraphs (3) and (9)(C)). Nothing contained in this subsection shall limit the authority of the Attorney General to exercise the discretion vested in him under section 1181(b) of this title. The first sentence of this subsection shall not apply to an alien who has been convicted of one or more aggravated felonies and has served for such felony or felonies a term of imprisonment of at least 5 years.
8 U.S.C. § 1182(c) (1994).
.Section 245(a) provides in pertinent part:
The status of an alien who was inspected and admitted or paroled into the United States or the status of any other alien having an approved petition for classification under subparagraph (A)(iii), (A)(iv), (B)(ii), or (B)(iii) of section 1154(a)(1) of this title may be adjusted by the Attorney General, in his discretion and under such regulations as he may prescribe, to that of an alien lawfully admitted for permanent residence *102if (1) the alien makes an application for such adjustment, (2) the alien is eligible to receive an immigrant visa and is admissible to the United States for permanent residence, and (3) an immigrant visa is immediately available to him at the time his application is filed.
8 U.S.C. § 1255(a) (footnote omitted).
. Pursuant to its reorganization under the Bureau of Homeland Security, the former INS now is called the Bureau of Citizenship and Immigration Services ("BCIS”). For consistency with the District Court opinions in this case, we continue to refer to the relevant agency as the "INS.”
. Prior to AEDPA § 440(d), only aliens convicted of an aggravated felony that resulted in a prison term of five or more years were explicitly precluded from seeking § 212(c) relief. 8 U.S.C. § 1182(c) (1994); see note 2, ante (text of provision). Under AEDPA § 440(d), however, § 212(c) relief became unavailable to aliens convicted of any aggravated felony (regardless of the associated prison term), almost all drug offenses, certain weapons or national security violations, or multiple crimes of moral turpitude. AEDPA § 440(d), 110 Stat. at 1277; see Drax II, 178 F.Supp.2d at 302.
. In June 1998, upon Drax’s release from prison after serving his criminal sentence, the INS took Drax into custody pursuant to the order of deportation. Drax was released from INS custody on or about July 10, 1998, after the posting of an immigration bond.
. Section 106(c) stated, in pertinent part:
Exhaustion of administrative remedies or departure from the United States; disclosure of prior judicial proceedings.
An order of deportation or of exclusion shall not be reviewed by any court if the alien has not exhausted the administrative remedies available to him as of right under the immigration laws and regulations or if he has departed from the United States after the issuance of the order.
8 U.S.C. § 1105a(c) (1994).
. For a detailed discussion of the complicated "adjustment of status” process, see Discussion, section III.B.l, post.
. Although Drax did not make such an argument in INS proceedings, the District Court again liberally construed Drax's pro se request to the Immigration Judge for "any kind" of relief and for "any type of a waiver” as having properly presented and exhausted this claim. Drax II, 178 F.Supp.2d at 306.
. Former § 241(a), 8 U.S.C. § 1251(a)(2)(C) (1994), as amended by INTCA § 203(b)(1), provided:
(C) Certain firearm offenses Any alien who at any time after entry is convicted under any law of purchasing, selling, offering for sale, exchanging, using, owning, possessing, or carrying, or of attempting or conspiring to purchase, sell, offer for sale, exchange, use, own, possess, or carry, any weapon, part, or accessory which is a firearm or destructive device (as defined in section 921(a) of title 18) in violation of any law is deportable.
Id. (emphasis added).
In 1996, § 241 was renumbered by IIRIRA as INA § 237, and codified at 8 U.S.C. § 1227 (2000). See IIRIRA § 305(a)(2), 110 Stat. at 3009-598. For consistency with the proceedings below, we refer throughout this opinion to § 241, instead of § 237.
. The Government had the opportunity to, and indeed did, oppose Drax's renewed claim of entitlement to Gabryelsky relief in its reply brief on appeal. We have considered the arguments raised therein, as well as the similar arguments raised by the Government in its Rule 59(e) motion for reconsideration before the District Court.
. We note that we have jurisdiction to entertain Drax’s Gabryelsky claim notwithstanding the absence of a certificate of appealability. In cases brought under 28 U.S.C. § 2254, we have held that in order to comply with 28 U.S.C. § 2253(c), a petitioner defending against an appeal by the Government must obtain a certificate of appealability in order to challenge claims denied by the District Court. See Grotto v. Herbert, 316 F.3d 198, 209 (2d Cir.2003). However, the § 2253(c) requirement does not apply to federal habeas proceedings, such as the instant one, brought pursuant to 28 U.S.C. § 2241. See 28 U.S.C. § 2253(c); Murphy v. United States, 199 F.3d 599, 601 n. 2 (2d Cir.1999) (collecting cases).
. “Prior to [AEDPA and IIRIRA], the law distinguished between deportation and exclusion proceedings. Aliens who were physically presentan the United States were placed into deportation proceedings. Exclusion proceedings dealt with aliens who were literally at the border seeking entry as well as those who had been physically paroled into the country but who, through a legal fiction, remained for immigration purposes at the border.” Henderson v. I.N.S., 157 F.3d 106, 11 n. 5 (2d Cir. 1998) (citing 8 U.S.C. § 1252b (repealed 1996)). "The 1996 law combined the two proceedings into a new process known as a 'removal proceeding.’ ” Id. (citing 8 U.S.C. § 1229a (added by IIRIRA)).
. INTCA § 203 provides as follows:
Sec. 203. Clarification of Certain Grounds for Exclusion and Deportation
(a) Exclusion Grounds. — -Section 212 of the Immigration and Nationality Act (8 U.S.C. 1182) is amended — •
(1) in subsection (a)(2) (A) (i)(I), by inserting "or an attempt or conspiracy to commit such a crime” after "(offense)”,
(2) in subsection (a)(2)(A)(i)(II), by inserting “or attempt” after "conspiracy”, and
(3) in the last sentence of subsection (h), by inserting ", or an attempt or conspiracy to commit murder or a criminal act involving torture” after "torture”.
(b) Deportation Grounds. — Section 241(a) of such Act (8 U.S.C. 1251(a)) is amended—
(1) in paragraph (2)(C)—
(A) by striking "in violation of any law,” and inserting ", or of attempting or conspiring to purchase, sell, offer for sale, exchange, use, own, possess, or carry,”, and
(B) by inserting "in violation of any law” after "(Code)”; and
(2) in paragraph (3)(B), by inserting "an attempt or” before "a conspiracy” each place it appears in clauses (ii) and (iii).
(c)Effective Date. — The amendments made by this section shall apply to convictions occurring before, on, or after the date of the enactment of this Act.
INTCA § 203, 108 Stat. at 4311.
. Prior to the INTCA, only completed weapons offenses (that is, non-attempt weapons offenses) rendered an alien deportable without recourse to § 212(c) relief. Completed weapons offenses were deportable crimes under 8 U.S.C. § 1251(a)(2)(C) (1994), that "could conceivably” have had an analogous ground of exclusion under § 212(a), but did not. See Cato, 84 F.3d at 602. In INTCA § 203, Congress added a number of attempt crimes to the corresponding list of completed crimes that constitute excludable and deport-able offenses. It appears that Congress made attempted weapons offenses deportable, but not excludable, because completed weapons offenses were already deportable, but not ex-cludable, crimes.
. Nothing in Gelman v. Ashcroft, 298 F.3d 150 (2d Cir.2002), in which we remanded to the BIA for reconsideration of the retroactive effect of § 602 of the Immigration Act of 1990, 104 Stat. at 5077, in light of St. Cyr, suggests otherwise.
. We note that even if the District Court were correct in holding that the INTCA does not apply retroactively, it is doubtful that such a holding could afford a proper ground for relief because it does not appear that Drax has exhausted his administrative remedies with respect to that claim. Drax did not make any argument regarding the nonre-troactivity of the INTCA either before the Immigration Judge or the BIA — despite the Government's argument that his attempted weapons conviction was a deportable offense. Former INA § 106(c) states that "[a]n order of deportation or of exclusion shall not be reviewed by any court if the alien has not exhausted the administrative remedies available to him as of right under the immigration laws and regulations.” 8 U.S.C. 1105a(c) (1994) (applicable to deportation proceedings commenced prior to April 1, 1997; current exhaustion statute at 8 U.S.C. § 1252(d) (2000)).
Although the Government’s exhaustion argument is potentially dispositive as a threshold matter, we do not reach the exhaustion question because we believe that consideration of the merits of the District Court's holding — which we deem to be erroneous — is essential to clarifying this complex area of the law. We have previously considered the merits of unexhausted immigration claims where we believed it important to do so. See, e.g., United States v. Gonzalez-Roque, 301 F.3d 39, 46 (2002) (rejecting a claim on the merits and also holding the claim was unexhausted); Correa v. Thornburgh, 901 F.2d 1166, 1171-72 (1990) (same).
. Former 8 C.F.R. § 245.1(e) (1993) provided for ”[c]oncurrent applications to overcome exclusionary grounds,” and stated in pertinent part that "[a]ny applicant for adjustment [of status] may also apply for the benefits of section 212(c) of the Act.” 8 C.F.R. § 245.1(e) (1993). The text of the regulation applicable to Drax's hearing before the Immigration Judge in 1997, 8 C.F.R. § 245.1(f) (1997), is identical to the 1993 regulation relied on by the BIA in Gabryelsky. The current version of the regulation, which has been amended to reflect the changes to the immigration laws in AEDPA and IIRIRA, is codified at 8 C.F.R. § 245.1(f) (2003).
. Drax’s claim for Gabryelsky relief was properly exhausted in INS proceedings. Drax’s assertion that he is eligible for Gabryel-sky relief is merely an extension of the argument his counsel raised directly before the BIA- — that the Immigration Judge erred in holding that no relief was available on account of the retroactive application of AEDPA § 440(d).
. Drax pleaded guilty to his drug offense on April 12, 1996, twelve days prior to the enactment of AEDPA.
. For the text of this provision, see note 3, ante.
. Drax, as the unmarried child of a United States citizen during the course of his deportation proceedings, would be considered a "first-preference alien." See 8. U.S.C. § 1153(a)(1) (classifying the unmarried children of a United States citizen in the first of several preference categories).
. An 1-130 petition may be filed by aliens in certain preference categories concurrently with an 1-485 application for adjustment of status where, "at the time of filing, approval of a visa petition ... would make a visa immediately available to the alien beneficiary.” 8 C.F.R. § 245.2(a)(2)(i)(B) (emphasis added). This exception is inapplicable to Drax because it is clear that, at any relevant filing time, he would have had to wait a significant amount of time before approval of a visa petition would render a visa "immediately available.” See Discussion, section III.B.2-3, post.
. In Gonzalez-Roque, 301 F.3d at 42, we stated that the filing of an 1-130 petition, “if approved, would have made an immigrant visa immediately available to [the alien].” Although that statement may have been correct in the context of that case, an approved 1-130 petition alone is not sufficient to render an immigrant visa "immediately available.” In order to be "immediately available," an immigrant visa must also be available to aliens with the relevant priority date in the appropriate preference category.
. The Immigration Judge has broad discretion to adjourn proceedings in order to enable an alien to file the necessary paperwork to seek various kinds of relief. See 8 C.F.R. § 3.31(c) (allowing the Immigration Judge to "set and extend time limits for filing applications and related documents” in immigration proceedings (emphasis added)); 8 C.F.R. § 240.6 (granting the Immigration Judge discretion to grant "a reasonable adjournment either at his or her own instance or, for good cause shown, upon application” by the parties). Indeed, in Gonzalez-Roque, 301 F.3d at 41-43, the same Immigration Judge who presided over Drax's hearing — Immigration Judge Joe Miller — granted the petitioner three separate adjournments to permit that petitioner's stepfather to file an 1-130 petition and thereby begin the adjustment of status process.
As Drax's counsel points out, a continuance of 15. months would not be inordinately long, in light of the fact that scheduling a hearing on Drax’s claim for § 212(c) discretionary relief (the other component of Drax’s putative Gabryelsky relief claim) frequently takes a year or more. See Pet’r’s Br. at 17 n. 6 (citing U.S. Gen. Accounting Office, Immigration Control: Deporting and Excluding Aliens from the United States (Report to the Chairman, Subcommittee on Immigration, Refugees, and International Law, Committee on the Judiciary, House of Representatives), GAO/GGD-90-18, at 40-43 (1989), available at http://archive.gao.gov/f0302/140072.pdf).
. The applicable regulations provide that once deportation proceedings have commenced, an 1-485 application can be "made and considered only in those proceedings.” 8 C.F.R. § 245.2(a)(1).
. This case raises an interesting jurisprudential question as to whether the Immigration Judge’s mistake — based on his good-faith understanding of the law as delineated by the relevant authorities available at the time the petitioner's immigration hearing — can properly be considered error. However, we need not entertain this question, as the Supreme Court has instructed in St. Cyr that an Immigration Judge’s legal error as to the availability of § 212(c) relief, based on a mistaken view of the retroactive application of AEDPA and IIRIRA, is an error that can and must be corrected in a habeas corpus proceeding. See generally St. Cyr, 533 U.S 289, 121 S.Ct. 2271.
.Because Drax's April 2000 marriage occurred while he was subject to deportation proceedings, he will have to demonstrate "by clear and convincing evidence to the satisfaction of the [Immigration Judge] that the marriage was entered into in good faith and in *119accordance with the laws of the place where the marriage took place and the marriage was not entered into for the purpose of procuring the alien’s admission as an immigrant and no fee or other consideration was given.” 8 U.S.C. § 1255(e)(3).