CALABRESI, Circuit Judge:

Relying upon our recent decision in Michael v. INS, 48 F.3d 657 (2d Cir.1995), William K. Kyei invokes this court’s jurisdiction under the All Writs Act, 28 U.S.C. § 1651(a), and petitions for a stay of deportation pending the Board of Immigration Appeals’ (“BIA’s”) ruling on his motion to reopen his deportation proceedings. Although *280 the normal, statutorily-contemplated avenues of temporary relief have been open to Kyei from the date of his deportation order, he has failed to pursue them. It follows that Kyei’s petition for a stay does not present the type of “extraordinary” case that we confronted in Michael, 48 F.3d at 663. Accordingly, we deny his petition. 1

BACKGROUND

Kyei is a native and citizen of Ghana, who entered the United States without inspection in March 1985. Pursuant to the Special Agricultural Workers (“SAW”) program of the Immigration Reform and Control Act of 1986, Pub.L. No. 99-603, 100 Stat. 3359 (“IRCA”) (codified at 8 U.S.C. § 1160), Kyei was granted lawful temporary resident status on February 20, 1992. This status applied retroactively to January 20, 1988, the date that Kyei first applied for SAW consideration. By operation of statute, Kyei also became a lawful permanent resident alien, effective retroactively as of December 1, 1990. See 8 U.S.C. § 1160(a)(2)(B); 8 C.F.R. § 210.5(a)(2).

On January 28, 1992, Kyei returned to the United States after having taken a brief trip to Holland. His travel plans were ill-conceived. Upon arriving at John F. Kennedy International Airport in New York, Kyei was arrested when an x-ray of his abdomen revealed that he was carrying several heroin-filled balloons in his stomach. On August 7, 1992, Kyei was convicted in the United States District Court for the Eastern District of New York of heroin importation in violation of 21 U.S.C. § 952(a). The court sentenced him to 37 months’ imprisonment, to be followed by three years of supervised release.

The Immigration and Naturalization Service (“INS”) started deportation proceedings on July 1, 1994, charging Kyei with being deportable for having been convicted of an aggravated felony. See 8 U.S.C. § 1251(a)(2)(A)(iii). On August 15, 1994, a hearing was convened before an Immigration Judge (“IJ”) in Oakdale, Louisiana, where Kyei was being detained. Over the course of four months, the IJ adjourned the deportation proceedings six times: first, so that Kyei could obtain a lawyer; then, to permit Kyei to change lawyers; and on four other occasions to allow Kyei’s lawyers more time to prepare their client’s case.

On October 11, 1994, Kyei was released from INS custody on a $30,000 bond, and he returned to his home in The Bronx. On November 3,1994, Kyei filed a motion before the IJ in Oakdale to change the venue of his deportation proceedings to New York City on the grounds that his family and supporting witnesses were located in the New York area. The INS opposed Kyei’s motion, and the IJ denied it on November 9, 1994.

Finally, on January 11,1995, Kyei’s deportation hearing resumed by telephonic conference. Kyei, through his New York attorney, conceded deportability, but noted that he had acquired temporary resident status under the SAW program in February 1988. Kyei’s attorney further indicated that his client wanted to apply for political asylum. Because of an attomey/client strategy disagreement, however, Kyei’s lawyer then requested that the IJ discharge him from the case. Kyei, who was also party to the telephone conversation, confirmed that he wished to dismiss his lawyer and to obtain another one. When the IJ informed Kyei that he was statutorily ineligible for any relief from deportation, including a discretionary waiver of deportation under section 212(c) of the Immigration and Nationality Act of 1952, 8 U.S.C. § 1182(c), Kyei responded that he wished to discuss the matter with a different attorney. The IJ refused to adjourn the hearing further, explaining that he had given Kyei since August 15, 1994 to find counsel and to resolve the matter. The IJ then concluded that Kyei was ineligible for any relief from deportation, and ordered him deported to Ghana.

Kyei appealed the IJ’s ruling to the BIA In the space on the notice-of-appeal form where an alien is directed to state the legal and factual bases for BIA review, Kyei simply wrote: “To set political asylum[.] Need *281 an attorney.” On April 7, 1995, the BIA summarily dismissed the appeal on the grounds that Kyei had been “provided ample opportunity to obtain counsel,” and that “he ha[d] not indicated any specific error in the decision of the immigration judge or in any of the procedures followed in the proceeding below.” Kyei did not seek judicial review of the BIA’s ruling in this or the Fifth Circuit.

On May 8, 1995, Kyei received from the INS a notice directing him to surrender for deportation on May 24, 1995 in Oakdale, Louisiana. Ten days after receiving this notice, Kyei filed a motion with the BIA to reopen his proceedings and to remand them to the IJ. He also requested a stay of deportation. In his motion papers, Kyei claimed that two errors had occurred in connection with his January 11,1995 deportation hearing. First, Kyei claimed that his lawyer erroneously failed to assert that he was eligible to apply for section 212(c) relief. Second, Kyei argued that the M’s determination— that he was statutorily ineligible for section 212(c) relief because he had not completed seven years of lawful permanent residence— was also in error.

According to Kyei, he began accruing lawful domicile for the purpose of achieving eligibility for section 212(c) relief on November 6, 1986 — the date of IRCA’s enactment. 2 Thus, in Kyei’s view, he had already met the seven-year statutory threshold before his lawyer conceded his deportability on January 11, 1995. In addition, Kyei argued that because his temporary resident status was originally made retroactive to the date of his SAW program application, January 20, 1988, he had, in any event, attained the requisite seven years lawful domicile in the United States during the period of his then on-going deportation proceedings. Nowhere in his motion to reopen, however, did Kyei raise any issue of potential conflicts between Fifth Circuit law and Second Circuit law regarding an alien’s statutory eligibility for section 212(c) relief.

The INS opposed Kyei’s motion to reopen and his stay application before the BIA. On May 24, 1995, Kyei surrendered for deportation in Oakdale. Six days later, the BIA denied Kyei’s request for a stay of deportation. At that point, Kyei did not seek a stay from the appropriate INS District Director. See 8 C.F.R. § 243.4 (authorizing District Director to grant a stay). Consequently, he did not, and, in fact, could not seek a stay of deportation by petitioning a federal district court for habeas corpus relief. See Garay v. Slattery, 28 F.3d 744, 745-46 (2d Cir.1994) (an alien may immediately challenge an INS District Director’s denial of a stay of deportation by writ of habeas corpus); 8 U.S.C. § 1105a(a)(10). Instead, on June 21, 1995, Kyei filed a petition in this court for a stay of deportation under the All Writs Act pending the BIA’s disposition of his motion to reopen, and a separate motion for a stay of deportation pending the court’s determination of his All Writs Act petition. The court granted Kyei a temporary stay of deportation in order to allow a sitting panel to consider his request more fully.

Finally, on June 23, 1995, Kyei applied to the local INS District Director in Louisiana for a stay of deportation. As of the date of oral argument on Kyei’s All Writs Act petition, the District Director had not yet ruled on Kyei’s administrative stay application.

DISCUSSION

In Michael v. INS, this court held that, “as ‘a residual source of authority to issue writs that are not otherwise covered by statute,’ ... the All Writs Act empowers federal courts of appeal[s] to stay orders of deportation in order to safeguard the court’s appellate jurisdiction.” 48 F.3d at 664 (quoting Pennsylvania Bureau of Correction v. United States Marshals Serv., 474 U.S. 34, 43, 106 S.Ct. 355, 361, 88 L.Ed.2d 189 (1985)). After determining that the petitioner in Michael had met this Circuit’s criteria for the issuance of a discretionary stay of deportation, we granted one. See 48 F.3d at 664-65. Understandably, Kyei now tries to align his own circumstances with those of the petitioner in Michael. We conclude, however, that *282 the two cases are distinguishable in any number of critical ways that preclude the invocation of our All Writs Act jurisdiction in favor of Kyei.

At the heart of our decision in Michael was the undisputed discrepancy that still exists between the settled law of the Fifth Circuit and the unsettled law of this circuit regarding the availability of section 212(c) relief for an alien who becomes deportable as a result of a firearms conviction. See id. at 662. The petitioner in Michael was a resident of Brooklyn, New York, and the INS had detained him in Oakdale, Louisiana. Oakdale is within the jurisdiction of the Fifth Circuit. Brooklyn is within the jurisdiction of the Second Circuit. In the Fifth Circuit, weapons-related deportees are ineligible to receive discretionary waivers of deportation under section 212(c). See id. (citing Rodriguez v. INS, 9 F.3d 408, 412-13 (5th Cir.1993)). In the Second Circuit, however, the question regarding the availability of section 212(c) relief for weapons-law violators remains open and under adjudication. See 48 F.3d at 662 (citing Esposito v. INS, 987 F.2d 108, 111-12 (2d Cir.1993)).

The petitioner in Michael argued that, absent a stay of deportation from this court, he was at risk of losing his statutory right (as a resident of Brooklyn) to have the Second Circuit review and apply its own section 212(c) law to any adverse ruling of the BIA regarding his motion to reopen his deportation proceedings. See 48 F.3d at 662-63 (discussing 8 U.S.C. § 1105a(a)(2)’s venue provision for judicial review of final deportation orders, and analyzing cases that address which circuit’s law should apply under the statute). From the outset of his administrative proceedings, the petitioner in Michael not only expressed his desire to litigate his deportation in the circuit of his residence by repeatedly seeking to change venue from Louisiana to New York, see id. at 663, but he also did much more. From the very first, he

consistently argued before the IJ, the INS District Director, the BIA, and the federal district courts in both New York and Louisiana [that] the question of whether weapons violators [were] eligible for section 212(e) relief remainfed] open in [the Second] Circuit.

Id. at 662.

Thus, by the time Michael sought a stay of deportation in this court, he had already: (1) pursued every administrative and judicial remedy contemplated by the immigration statutes; (2) argued to each of those bodies that he was potentially eligible for section 212(c) relief under Second Circuit law (a forum to which he had a statutory right of appeal); and (3) been rebuffed in every forum without consideration of his likelihood of success in the Second Circuit. Taking all of these factors into consideration, we concluded that our jurisdiction over Michael’s ultimate appeal was “both at issue and at risk.” Id. at 663.

Kyei argues that his fate, like Michael’s, is crucially affected by a split between Fifth and Second Circuit law. Kyei first contends that the Second Circuit, in determining an alien’s statutory eligibility for discretionary relief, does not equate section 212(e)’s requirement that an alien have seven years of “lawful unrelinquished domicile” with the provision’s reference to “lawful permanent residence.” See Lok v. INS, 548 F.2d 37, 41 (2d Cir.1977) (“Lok I ”). He also asserts that the Fifth Circuit, in contrast, follows the BIA’s interpretation of the section 212(c), which does equate the concepts of lawful domicile and lawful permanent residence. Thus, Kyei insists that he is eligible for section 212(e) consideration under the Second Circuit rule, but is ineligible under the Fifth Circuit rule because he was only lawfully domiciled in the United States since January 20, 1988.

There is a second level to his argument. As stated above, Kyei, through his attorney, conceded deportability at his deportation hearing on January 11, 1995. This was nine days before he would have attained the seven years of lawful domicile that is necessary for section 212(c) eligibility under our rule in Lok I — i.e., January 20, 1995. To overcome this hurdle, Kyei next argues that our decision in Vargas v. INS, 938 F.2d 358 (2d Cir.1991), permits an alien to reopen a deportation proceeding in order to apply for section 212(c) relief even after a final order of *283 deportation has issued. In contrast, Kyei notes that it is well settled in the Fifth Circuit that an alien cannot move to reopen deportation proceedings to obtain section 212(c) consideration once the BIA affirms the deportation order or the order otherwise becomes administratively final. See Ghassan v. INS, 972 F.2d 631, 637 (6th Cir.1992). Kyei argues that this second split in circuit law provides a further justification for this court to intervene in order to preserve its appellate jurisdiction. 3

Initially we note that these purported disparities between the law of the Fifth and Second Circuits are more than dubious. To begin with, we question Kyei’s assertion that the Fifth Circuit has adopted the BIA’s seven year “lawful permanent residence” requirement for section 212(c) eligibility. Apparently, the Fifth Circuit has yet to choose between our interpretation of section 212(c)’s eligibility requirements as stated in Lok I and the BIA’s reading of the statutory provisions. See Madrid-Tavarez v. INS, 999 F.2d 111, 112 (5th Cir.1993); see also Castellon-Contreras v. INS, 45 F.3d 149, 152 (7th Cir.1995) (citing Madridr-Tavarez and noting that the Fifth Circuit has “discussed, but not adopted, either the BIA or Lok I position”). Consequently, we doubt that Kyei can demonstrate the kind of head-to-head conflict on this point that might foreclose the possibility of relief in the Fifth Circuit, while, at the same time, offer hope in this court.

Similarly, the government asserts that our decision in Vargas does not help Kyei. In Vargas, we stated that “an alien cannot become eligible for discretionary relief through subsequent accrual of time towards the seven-year threshold, once he has conceded that he is deportable.” 938 F.2d at 361 (construing Lok v. INS, 681 F.2d 107, 110 (2d Cir.1981) (“Lok II”)). Because Kyei conceded deportability nine days before he would have become eligible to apply for a discretionary waiver of deportation, the government argues that he is barred in this circuit, as well as in the Fifth Circuit, from reopening his cases to seek section 212(c) relief. Kyei replies that this particular language in Vargas is merely dictum, and therefore not binding in this case. He in effect urges us to reject this supposed dictum and create a conflict with Fifth Circuit law on this point.

We need not address the merits of this dispute, however. Until Kyei sought a stay of deportation in this court, he had never raised the issue of divergent circuit law and had not asserted his eligibility for a stay based on his substantive rights under the Second Circuit law in any administrative or judicial arena. This fact alone completély distinguishes his case from Michael. In Michael, the petitioner first presented his argument concerning the availability of relief under Second Circuit law to the IJ in Oakdale in his initial motion for a change of venue. 4 *284 He subsequently pressed that same argument in every forum in which he sought a stay. See 48 F.3d at 659-60. Kyei, on the other hand, never argued to the IJ that there was a divergence in the law of the Second and Fifth Circuits. Nor did he present it to the BIA — on direct appeal from the IJ’s ruling or in his motion to reopen. And before lodging the instant petition in this court, Kyei did not seek a stay from the INS District Director on the basis of such a conflict. Instead, Kyei first raised his conflict-of-law claim in this court and in the context of seeking an extraordinary remedy of last resort.

By issuing a stay of deportation under the All Writs Act in Michael, “we by no means intended] to create a method by which aliens Contesting deportation may circumvent” the standard statutory review procedures. 48 F.3d at 665 n. 8. To the contrary, we explained that “[i]t is only when no other means of review are available ... that the All Writs Act becomes available.” Id. We adhere to that view today.

Accordingly, we hold that before an alien can seek a stay of deportation under the All Writs Act on the ground that the law of the circuit of his or her residence provides a colorable claim for relief, while the law of the circuit in which he or she is being administratively processed does not, that alien must pursue — on the basis of that claim — all plausible avenues of temporary relief established by the immigration statute and regulations. First, the alien must exhaust all administrative remedies by clearly presenting the divergence-of-law claim to the IJ, the BIA, and the local INS District Director. Should that fail to provide a stay, the alien must next turn to a federal district court for habeas relief as provided by statute. See Garay, 23 F.3d at 745-46 (“A petitioner may seek habe-as relief from a denial of a stay by the District Director, but not from a denial of a stay by an immigration judge or by the BIA pending the disposition of a motion to reopen proceedings.”); 8 U.S.C. § 1105a(a)(10). Only after an alien has been effectively denied habeas consideration — and our court’s statutory jurisdiction to decide serious conflicts involving residents of this circuit, according to the law of this circuit, is endangered — may he or she then seek a stay of deportation under the All Writs Act here. 5

This procedure, we think, is not only mindful of the statutory framework that provides for judicial review of final deportation orders both at the habeas level and ultimately by the court of appeals in the alien’s residence, see 8 U.S.C. § 1105a, but it is also appropriately deferential to the system’s administrative foundation. It seems obvious to us that the primary consideration of these sorts of stay requests must lie with the agency that is both charged with the efficient implementation of our immigration laws and that is actually invested with the power to provide the relief sought. To hold otherwise would interfere with the INS’s and BIA’s ability to develop a comprehensive law enforcement policy, and would do so for no good reason.

Kyei disagrees.. He argues that because the IJ, BIA, INS District Director, and the federal district court in Louisiana are required to apply Fifth Circuit precedent, see, e.g., Ithaca College v. NLRB, 623 F.2d 224, 228 (2d Cir.1978), cert. denied, 449 U.S. 975, 101 S.Ct. 386, 66 L.Ed.2d 237 (1980), it would be futile for him to request a stay in those *285 fora based upon Second Circuit law. But this response misses the mark.

Issuing a stay of deportation, which is based upon an alien’s colorable opportunity to obtain relief from the Second Circuit, by exercising his or her statutory right to appeal from a final deportation order to the Second Circuit, does not require either agency officials or federal district judges to ignore the law of the circuit in which they operate. Indeed, they could very well believe that the alien would lose on the merits of his or her motion to reopen were that issue to be determined under local circuit law, and still stay the deportation order to permit the alien to seek relief on the merits in the circuit of his or her residence, as provided by the statute which establishes venue for review in either — but not in both — circuits. Indeed, given our admonishment in Michael that the petitioner’s “application for a stay of deportation should have been granted by the IJ because this Circuit would have granted such a stay,” 48 F.3d at 665 (emphasis added), we believe that the immigration authorities in the Fifth Circuit might very well have given due consideration to Kyei’s present divergenee-of-law claim had he presented it to them. We certainly cannot assume, as Kyei would have us do, that they would have denied what he never asked for.

CONCLUSION

The Supreme Court has cautioned that “[although the [All Writs] Act empowers federal courts to fashion extraordinary remedies when the need arises, it does not authorize them to issue ad hoc writs whenever compliance with statutory procedures appears inconvenient or less appropriate.” Pennsylvania Bureau of Correction, 474 U.S. at 43, 106 S.Ct. at 361. Because Kyei never attempted to pursue his remedies under the immigration statute, we will not entertain his request for a stay of deportation under the All Writs Act. Accordingly, we deny his petition.

. After hearing oral argument on the petition, the panel denied Kyei's request for a stay of deportation and advised the parties this written opinion would follow.

. This claim, in turn, rests upon the fact that IRCA prohibited the INS from deporting those aliens who could present nonfrivolous claims of eligibility for temporary resident status under its provisions. See 8 U.S.C. § 1160(d)(1).

. In the alternative, Kyei reasserts the argument that he presented to the BIA on his motion to reopen. He claims that his necessary seven-years of lawful domicile began to accrue on November 6, 1986 (the date of IRCA's enactment) because, as an alien who was prima facie eligible for temporary resident status, IRCA prohibited the INS from freely deporting him. This argument need not detain us long. Although we do not address the merits of Kyei’s alternative argument now, we note that neither the Fifth Circuit nor this court has ever specifically ruled on it. This claim therefore plainly involves no troublesome split in circuit law. Nor does it present “a non-frivolous [issue] of constitutional dimension,” which might trigger a deeper judicial concern. See Michael, 48 F.3d at 664-65 (citing Blancada v. Turnage, 891 F.2d 688, 690 (9th Cir.1989)). Consequently, we do not think that it merits any consideration in the context of an All Writs Act petition for extraordinary relief.

. We acknowledge that Kyei also sought a change of venue to litigate his deportation in the Second Circuit. But while seeking a change of venue might perhaps be a necessary condition for obtaining an All Writs Act stay of deportation, it is certainly not a sufficient one. In addition to setting forth the important considerations of family and other defense-related ties to the circuit of the alien’s residence, a requested venue change— in order to have any weight in the consideration of a subsequent All Writs Act petition — must specifically set forth a meaningful distinction between the laws of the circuits involved.

We do, however, take this opportunity to express our concern over what appears to be an unstated policy of the INS to oppose all motions to change the venue of deportation proceedings, and to do so even in cases where an alien has been released from custody on bond. We regularly observe that, as a result of this seeming policy, bonded aliens are denied the opportunity to litigate their deportations in the circuit of their residence. Not only does this deprive such aliens of family support and other resources essential to their defense, it also leads to telephone *284 "hearings” that are always undesirable and occasionally of dubious validity. We appreciate that the concentration of administrative processes in one forum has some efficiency benefits for the government. But we also note that venue transfers may actually result in more efficient adjudication — particularly if the petitioner will ultimately choose to seek review in another circuit.

. "Of course, the simple fact that jurisdiction exists ... does not necessarily mean that we should exercise our powers under it.” Michael, 48 F.3d at 664. For example, we could always decline to issue a stay if we believed that the habeas court had appropriately considered the substantive law of this circuit.

In the event that a habeas court is not responsive to the exigencies of a particular case (including delays in issuing rulings on the part of the INS District Directors), and where the threat of deportation is imminent, a simultaneous resort to an All Writs Act stay petition may be warranted. In deciding this case, however, we need not determine when this might be so or, for that matter, the extent to which an alien must continue to litigate a federal habeas claim before he or she may seek All Writs Act relief. As previously noted, Kyei never sought habeas relief at all.