OPINION

Robert Edward Beaton is a native and citizen of Guyana. He was convicted of a controlled substance violation and was deported in June of 1994. He reentered the United States in February 1995, and on December 7, 1999, he was convicted of illegal entry subsequent to a conviction for commission of an aggravated felony under 8 U.S.C. § 1826(b)(2). The Government issued a new Notice to Appear in March 2000, based on the December 1999 conviction. On February 21, 2003, an Immigration Judge (IJ) found Beaton deportable, finding that his conviction for illegal entry after deportation was an aggravated felony under INA § 101(a)(43)(O) [8 U.S.C. § 1101(a)(43)(O) ]. The IJ found him ineligible for relief, and the Board of Immigration Appeals (BIA) affirmed on February 18, 2004.

Before us are two matters that have been consolidated for disposition. The first, docketed at C.A. No. 05-3517, originated as a motion filed on January 24, 2005, pursuant to 28 U.S.C. § 2255 in the United States District Court for the Western District of Texas. Attached to the motion was an order of the Superior Court of the District of Columbia, dated December 30, 2004, granting Beaton’s motion to vacate a controlled substance conviction, and the Government’s motion to dismiss the indictment in the case. The § 2255 motion argued that because this conviction had been vacated, Beaton’s conviction for illegal entry subsequent to a conviction for commission of an aggravated felony was invalid, and that the removal order was also resultantly invalid. The motion asked the Court to vacate or set aside the reentry charge and the removal order, and to release him from custody. The Court construed the petition as one filed pursuant to 28 U.S.C. § 2241 and transferred the petition to the United States Court of Appeals for the Fifth Circuit pursuant to the Real ID Act of 2005, § 106(c), Pub.L. No. 109-13, Div. B, 119 Stat. 231 (May 11, 2005). The Fifth Circuit court in turn transferred the petition to our Court, as the IJ completed proceedings in this ease in York, Pennsylvania. See 8 U.S.C. § 1252(b)(2) (“The petition for review shall be filed with the court of appeals for the judicial circuit in which the immigration judge completed the proceedings.”). To the extent the original § 2255 motion challenged Beaton’s order of removal, we treat it as a timely-filed petition for review. See Bonhometre v. Gonzales, 414 F.3d 442, 446 (3d Cir. 2005). As explained below, to the extent the § 2255 motion challenged Beaton’s conviction for illegal entry after deportation, we will transfer the motion back to the United States District Court for the Western District of Texas pursuant to 28 U.S.C. § 1631.

The second matter, docketed at C.A. No. 05-3988, originated as a petition for a writ of habeas corpus, filed March 8, 2004, pursuant to 28 U.S.C. § 2241 in the United *138 States District Court for the Middle District of Pennsylvania. In his petition, Beaton argued that the Government had retroactively and improperly applied INA § 241(a)(5) [8 U.S.C. § 1252(a)(5) ] to reinstate his prior deportation order. The Government filed a response, noting that Beaton’s prior deportation order had not been reinstated; rather, he had been served with a new Notice to Appear and that the removal order was based on the charges in that Notice. After giving the parties an opportunity to comment, on August 24, 2005, the Court transferred the § 2241 petition to this Court pursuant to the REAL ID Act.

Beaton filed a brief in each matter, raising the same issue: because his “criminal convictions were all dismissed and vacated including the conviction that resulted from the deportation order from which the reentry charge stemmed from,” the removal order should be dismissed and the reentry charge should be vacated. The Government filed a motion to consolidate the actions, and a motion for summary affirmance in lieu of a brief, which was filed in each of the actions. The Government’s motion for summary affirmance argues that this Court cannot consider the sole issue raised by Beaton, because the administrative “record contains no evidence that his convictions were dismissed,” and because Beaton did not raise the issue before the BIA. Beaton filed a response in opposition to summary affirmance, arguing that the Government has the burden to show the continued existence of his convictions, and that he could not have raised the issue before the BIA because the convictions had not yet been dismissed and vacated.

We agree with the Government that Beaton is required to exhaust his administrative remedies on the issue of whether his removal order has been rendered invalid by the vacation of his conviction(s). 1 The relevant statute provides that a “court may review a final order of removal only if ... the alien has exhausted all administrative remedies available to the alien as of right.” 8 U.S.C. § 1252(d)(1). Beaton filed an appeal to the BIA, thus, he completed his administrative remedies “as of right.” However, he could have filed (and might still be able to file) a motion to reopen. 2

Although reopening is not a remedy available as of right, we will require exhaustion here as a prudential matter. Factors to consider in deciding whether to require exhaustion as a prudential matter include whether “(1) agency expertise makes agency consideration necessary to generate a proper record and reach a proper decision; (2) relaxation of the requirement would encourage the deliberate bypass of the administrative scheme; and (3) administrative review is likely to allow the agency to correct its own mistakes and to preclude the need for judicial review.” Huang v. Ashcroft, 390 F.3d 1118, 1123 (9th Cir. 2004) (citations omitted). Here, the record before us is undeveloped as to the claim Beaton wishes to raise. See also, 8 U.S.C. § 1252(b)(4)(A) (court may only decide the petition on the administrative record on which the order of removal is based). Although motions to reopen are generally discouraged, where, as here, there is new information that goes to the heart of the removal order, requiring a motion to reopen will allow the agency to *139 review the matter in the first instance. Cf. Marrero v. INS, 990 F.2d 772 (3d Cir. 1993) (requiring alien to file motion to reopen with immigration court before he could challenge in absentia removal order). We therefore decline to reach the merits of Beaton’s arguments, because he has failed to exhaust administrative remedies.

As noted above, the § 2255 motion filed in the United States District Court for the Western District of Texas, eventually transferred and docketed here, appears to be, in part, a challenge to Beaton’s conviction for illegal entry after deportation. As his conviction was entered in the Western District of Texas; see A.R. 445-49, we will transfer the motion back to that Court pursuant to 28 U.S.C. § 1631. We express no opinion as to the merit of his § 2255 motion. 3