WINTER, Circuit Judge:

Wilfredo Zelaya was convicted after a jury trial before Judge Middlebrooks for illegally re-entering the United States after having been deported subsequent to a conviction for an aggravated felony. See 8 U.S.C. §§ 1326(a), (b)(2). On appeal, he argues that the district court erred when it denied his motion to dismiss the indictment on the ground that the order pursuant to which he was deported was invalid. He also contends that the district court erred by instructing the jury that, for purposes of the present case, the word "deportation" meant appellant's physical removal from this country, which was subsequent to his conviction, rather than the issuance of the deportation order, which was prior to his conviction. Because these arguments are without merit, we affirm.

I.

Appellant illegally entered the United States on or about July 15, 1993. Sometime around September 18, 1995, he was arrested and charged with sexual battery of a minor and was held in state custody pending his trial. On August 23, 1996, appellant pleaded guilty to the state charges and was sentenced to 364 days of incarceration to be followed by fifteen years of probation. Perhaps because of time served with various credits, the state court released appellant on that same day to begin serving his probation.

Near the time of appellant's arrest, the Immigration and Naturalization Service (the "INS") commenced a deportation proceeding against him. On September 27, 1995, the INS sent an order to show cause and a notice of hearing by certified mail to appellant's last known address. Following its usual practice, the INS requested and received a return receipt, confirming that someone had signed for and received the order and notice on October 4, 1995. On April 2, 1996, the INS conducted the deportation hearing. This hearing was in absentia because appellant did not appear and had not responded to the INS's notice. On the same day, the immigration judge issued a warrant for appellant's deportation.

His counsel states that appellant was unaware of the deportation proceeding because he was in state custody at the time. On May 10, 1997, almost a year after appellant's release from state custody, the INS arrested and processed him for removal pursuant to the deportation warrant. Appellant claims that the time of his arrest was when he first learned of the deportation order. On May 15, 1997, the INS physically deported appellant. On August 30, 1999, the INS found appellant in Florida's Dade County Jail, and he was thereafter charged with violating 8 U.S.C. §§ 1326(a), (b)(2) by re-entering the United States.

Appellant moved to dismiss the indictment. The motion claimed, inter alia, that the deportation order was not valid because it was entered without notice or an opportunity to be heard. The district court denied the motion. At trial, the government presented evidence showing that appellant: (i) had been convicted of an aggravated felony; (ii) had been deported from the United States pursuant to a warrant of deportation; and (iii) was subsequently found in this country. During its deliberations, the jury asked the district court: "Why is the date on the warrant of deportation of 4/2/96 prior to the date on stipulation of his `aggravated felony' conviction of 8/23/1996? Does this have bearing on [whether he was deported subsequent to his conviction]?" The district court answered: "Deportation [for these purposes] means the date the defendant was formally removed from the United States. The Warrant of Deportation . . . was signed on April 2, 1996 . . . and executed on May 15, 1997." The jury thereafter found appellant guilty, and the district court sentenced him to sixty-three months of imprisonment and two years of supervised release. This appeal followed.

II.

We turn first to appellant's claim that the deportation order was invalid. For purposes of Section 1326, the existence of a deportation order is an adjudicative fact to be proven by the government. See United States v. Henry, 111 F.3d 111, 113 (11th Cir. 1997). However, a defendant charged with violating that Section may collaterally challenge the validity of such an order in the criminal proceeding, see 8 U.S.C. § 1326(d), which is an issue of law to be reviewed de novo on appeal. See United States v. Fernandez-Antonia, 278 F.3d 150, 156 (2d Cir. 2002); United States v. Garcia-Martinez, 228 F.3d 956, 960 (9th Cir. 2000). To succeed, a collateral attack on a deportation order in such a criminal proceeding must show that: (i) the alien exhausted any administrative remedies that may have been available to seek relief against the order; (ii) the deportation proceeding at which the order was issued improperly deprived the alien of an opportunity for judicial review; and (iii) the entry of the order was fundamentally unfair. See 8 U.S.C. § 1326(d). Appellant's motion papers fell short of meeting any of these requirements.

Appellant admits that he did not exhaust his administrative remedies but maintains that his detention in state custody rendered him "factually and legally incapable" of seeking any administrative remedies. We disagree. INS policy specifically allows an alien such as appellant to request that a deportation order issued in absentia be rescinded. This request may be made "[a]t any time if the alien demonstrates that he or she did not receive notice or if the alien demonstrates that he or she was in federal or state custody and the failure to appear was through no fault of the alien." 8 C.F.R. § 3.23(b)(4)(iii)(A)(2); see also Anin v. Reno, 188 F.3d 1273, 1276 n. 4 (11th Cir. 1999) (discussing a predecessor code). Appellant therefore could have requested rescission even if he in fact learned of the deportation order for the first time on May 10, 1997. To be sure, he was deported shortly after that date. Nevertheless, he had a sufficient opportunity to petition for administrative relief, see United States v. Hinojosa-Perez, 206 F.3d 832, 836 (9th Cir. 2000), and, under the law at the time of appellant's deportation, his removal would have been automatically stayed by a motion pursuant to Section 3.23(b)(4)(iii) to rescind his deportation proceeding. See 8 C.F.R. § 3.2(f) (1997). Moreover, if appellant wanted to re-enter the United States and to do so legally, nothing precluded him from seeking a rescission of his deportation order even after his removal from the United States. He therefore failed to exhaust available administrative remedies.

Appellant's claim as to a deprivation of appellate review and the fundamental unfairness of the deportation order rests entirely on the purported lack of notice to him of the deportation proceeding. However, there are three fatal flaws in this claim.

First, there is no factual basis in the record establishing a lack of actual notice. The motion papers submitted by his counsel assert lack of notice as a fact, but they are not accompanied by an affidavit or other proffer of available evidence that might be offered at, and would trigger a need for, a factual hearing. Indeed, it is less than clear that the purported lack of notice is more than an inference drawn by counsel from the fact of appellant's being in state custody when the notice was sent. After the motion was denied, appellant testified at trial only that he had not known of the deportation order until his arrest.

Second, there is, as a matter of law, no flaw in the notice given, even if appellant did not receive it. Appellant was responsible for keeping the INS informed of his current address, see 8 U.S.C. § 1305(a); Dominguez v. United States Attorney Gen., 284 F.3d 1258, 1260 (11th Cir. 2002) (per curiam), and does not dispute that the INS sent him a notice by certified mail to the last address submitted by him. We have held that a mailing to the last known address is sufficient to satisfy the INS's duty to provide an alien with notice of a deportation proceeding. See Anin, 188 F.3d at 1277; see also Dominguez, 284 F.3d at 1260; United States v. Estrada-Trochez, 66 F.3d 733, 736 (5th Cir. 1995).

Third, "fundamental unfairness requires a showing that specific errors prejudiced the defendant." United States v. Holland, 876 F.2d 1533, 1536 (11th Cir. 1989). An alien characterizing a deportation as fundamentally unfair must, at a minimum, demonstrate that the outcome of the deportation proceeding would have been different but for a particular error. See id. at 1537. Appellant has not made even a suggestion that his knowledge of, or presence at, the deportation hearing would have altered the result. The district court did not, therefore, err in denying the motion.

III.

Appellant also maintains that the district court erred in instructing the jury as to the meaning of the word "deportation." As noted, the district court told the jury that, for purposes of 8 U.S.C. § 1326(b)(2), deportation was subsequent to a conviction when the alien is physically removed from the United States after the conviction even if the warrant for the deportation was issued before the conviction. We agree with the district court.

Although the statute does not define "deportation," appellant's proposed interpretation is meritless. Section 1326(b)(2) mandates a harsher punishment for an alien who, having been deported "subsequent to" committing an aggravated felony, illegally re-enters the United States. See Almendarez-Torres v. United States, 523 U.S. 224, 231-33, 118 S.Ct. 1219, 140 L.Ed.2d 350 (1998). Clearly, one purpose of the statute is to provide a greater deterrence to illegal entry by a deportee who has earlier committed a serious crime while in the United States. Given this purpose, a distinction giving weight to the fortuities of dates of deportation orders and convictions makes little sense, see United States v. Cooke, 850 F.Supp. 302, 306 (E.D.Pa. 1994); see also United States v. Guevara-Lopez, No. 96-1437, 1996 WL 440670, at *2 (1st Cir. Aug.6, 1996) (per curiam) ("That the aggravated felony was committed after an order of deportation was issued (but before the order was executed) does not at all reduce the seriousness of the crime of reentry or the need for a greater deterrent to reentry."), particularly in light of the fact that a deportation proceeding may begin as the result of attention drawn to the alien by an arrest but the deportation order may well be issued before the judgment of conviction is entered. Although there may be contexts in which the meanings of "deportation" and "warrant of deportation" overlap, the most common usage refers to deportation as an act rather than an order directing that act. We believe that the context here indicates that the common usage was intended.

IV.

For the reasons stated above, we AFFIRM.