Utter rubbish.
Hope they didn't charge you for that.
USCIS would LOVE for that to be the case, and their scary strongly worded denial letters appears that way, but it isn't legally accurate. You are a permanent resident, and you can live, work, and travel, and remain a permanent resident until a final order of removal, at which point you are no longer a permanent resident.
No ifs, no buts, that is the law. Unfortunately, as is common with the law as it has evolved, naturally it does contradict itself in places, since the whole I-751 requirement was added in the mid 80s on top of existing laws, but it has been clarified in multiple places, including EOIR appeals decisions.
It is firmly established as precedent in case law. Genco Opinion 96-12 sums it up best, and I quote (my bolding):
"96-12 Status of a conditional permanent resident after denial of I-751 during pendency of review by EOIR
August 6, 1996
Status of a Conditional Permanent
resident after denial of I-751 during
pendency of review by EOIR
Office of the
General Counsel
I. QUESTIONS
The Benefits Division requests a legal opinion concerning the following questions:
1) What is the status of a conditional permanent resident after his I-751 has been denied by the director and his case is under review by the EOIR? Is the alien entitled to an I-551 stamp, adapted to show that his case is pending? Is the alien entitled to any other benefits associated with legal permanent resident status?
2) If an Order to Show Cause has not been issued, what is the alien's status and what documentation is the alien entitled to possess?
II. SUMMARY CONCLUSION
The director should issue the Order to Show Cause at the time he or she provides written notice to the alien of the decision to deny the Form I-751.
Strictly speaking, a conditional permanent resident whose Petition to Remove Conditions on Residence (Form I-751) has been denied by the director is no longer a lawful permanent resident, as of the date of the director's notice of termination. However, because the alien has a right under statute and regulation to request review of such determination in deportation proceedings, the conditional permanent resident whose status has been terminated should be issued a temporary I-551 during the pendency of such review. INS should not approve any Petition for Alien Relative (Form I-130) filed by the alien on behalf of another alien during the pendency of such proceedings.
III. ANALYSIS
Section 216 of the Immigration and Nationality Act (INA), 8 U.S.C. § 1186a, provides that an alien spouse who is granted permanent resident status by means of marriage to a United States citizen which took place less than two years earlier shall be granted such status on a conditional basis. Unless otherwise specified by the statute or regulations, an alien granted permanent resident status pursuant to section 216 enjoys the same rights, privileges, responsibilities, and duties as other legal permanent residents. 8 C.F.R. § 216.1
The conditional basis of residence is removed via the approval of a Petition to Remove the Conditions on Residence (Form I-751) filed by the alien and spouse within 90 days before the second anniversary of the date on which the alien obtained lawful admission for permanent residence. The director of the regional service center has been delegated sole authority to adjudicate the Form I-751. 8 C.F.R. § 216.4(c). Where the director finds derogatory information pertaining to the validity of the marriage, he or she must offer the alien the opportunity to rebut such information. Id. If the alien is unable to overcome such derogatory information, the director ''may deny the joint petition, terminate the alien's permanent residence and issue an order to show cause to initiate deportation proceedings.'' Id. (emphasis added). Moreover, if the director proceeds to deny the Form I-751, he or she must provide written notice specifying the basis for the denial to the alien ''and shall issue an order to show cause why the alien should not be deported from the United States.'' 8 C.F.R. § 216.4(d)(2) (emphasis added). This regulatory language clearly provides that once the director denies the joint petition and terminates the alien's permanent residence, an order to show cause must follow.
The regulations further specify that the alien's lawful permanent residence status is terminated as of the date of the director's written decision. 8 C.F.R. § 216.4(d)(2). As of the date of denial, the alien is ''instructed to surrender any Alien Registration Receipt Card previously issued by the Service.'' Id. Accordingly, an alien whose Form I-751 has been denied has no status as a conditional permanent resident and is not entitled to an Alien Registration Receipt Card. Therefore, in light of the termination date of an alien's lawful permanent residence, and the gap that ensues if an order to show cause is not issued, failure to timely issue the order to show cause leaves INS vulnerable should an alien file an action in mandamus to compel performance of that requirement.
Concomitantly, an alien whose Petition to Remove Conditions on Residence has been denied by the director may seek review of the decision in deportation proceedings. INA § 216(c)(3)(D), 8 U.S.C. § 1186a(c)(3)(D), 8 C.F.R. § 216.4(d)(2). In fact, the statute specifically conditions termination of permanent resident status upon review in deportation proceedings. 1 Therefore, the terminated conditional lawful permanent resident should be issued a temporary Form I-551, during the pendency of the deportation proceedings. Cf. Etuk v. Slattery, 936 F.2d 1433, 1447 (2d Cir. 1991)(''To revoke an LPR's green card pending completion of the deportation process would severely undermine the integrity of the process itself and impose significant hardship on the alien involved''). To that end, the INS' policy of placing an I-551 stamp on an alien's I-94 arrival card or passport is considered appropriate temporary evidence of legal permanent resident status during the duration of the deportation proceedings. Memorandum from James J. Hogan, INS Executive Associate Commissioner (Nov. 11, 1992), reported and reproduced in 69 Interpreter Releases 1560 (Dec. 14, 1992). Further, the temporary I-551 may be used to travel, to establish employment eligibility, or to establish lawful permanent resident status for purposes of obtaining school financial aid and other benefits."
There is plenty more legalese and other links and chunks of text I could paste, but I can't be bothered right now.
As my circumstances have unfortunately dictated, I have a very intricate knowledge of the I-751 process, denial process, and what happens during and after, and my knowledge is increasing every day even now.
To put it bluntly, there is ZERO chance I would have travelled out of the US if my residency or ability to re-enter the US was in jeopardy after travelling post denial (all of them) if I was remotely unsure of the law here in these exact circumstances I have found myself in - identical to yours - on numerous occasions.
Just get the refiling in quickly, await the receipt number and get that new stamp as detailed before.
Probably for the best given that answer.