PER CURIAM:

Clifford Medley, Amarillo, TX, pro se. Nathan Tadema, Office of the Atty. Gen., Postconviction Lit. Div., Austin, TX, for Respondent–Appellee. Appeal from the United States District Court for the Northern District of Texas.

Before JOLLY, DeMOSS and DENNIS, Circuit Judges.

PER CURIAM:

The petition for panel rehearing is GRANTED. We withdraw our prior opinion, Medley v. Thaler, 400 Fed.Appx. 965 (5th Cir.2010) (per curiam), and substitute the following.

The petitioner, Clifford Scott Medley, appeals the dismissal of his habeas petition as untimely filed under the Antiterrorism and Effective Death Penalty Act (AEDPA), see 28 U.S.C. § 2244(d) (establishing a one-year statute of limitations for filing federal habeas petitions). He argues that we should treat his petition as having been timely filed because his prior unsuccessful effort to mail a habeas petition through his prison mail room, prior to the expiration of the one-year statute of limitations, entitles him to the benefit of the mailbox rule or equitable tolling of the statute of limitations. In our prior panel opinion, we concluded that Medley was entitled to neither. Medley, 400 Fed.Appx. at 965. We concluded that Medley was not entitled to the benefit of the mailbox rule, because his petition was returned to him by prison staff after he failed to comply with a reasonable prison mail regulation. Id. at 968–70.

Medley filed a petition for panel rehearing, explaining that after he filed his reply brief, he learned that the purported mail regulation does not actually exist. In his response, the respondent, Rick Thaler, the Director of the Texas Department of Criminal Justice, Correctional Institutions Division, concedes the same. Thus, we conclude that Medley attempted to mail his petition in a manner consistent with the mail regulations, and that he was prevented from doing so because prison mail room officials wrongfully returned it for failure to comply with a nonexistent prison mail regulation. Accordingly, we agree that Medley should have been afforded the benefit of the mailbox rule and that his petition should have been considered timely filed.

We therefore REVERSE the dismissal of Medley's petition and REMAND to the district court for further proceedings consistent with this opinion.

BACKGROUND

In March 2002, Medley was convicted of murder and sentenced to forty years imprisonment. On appeal, his conviction was affirmed, and, on November 7, 2005, the Supreme Court denied Medley's petition for certiorari. Medley v. Texas, 546 U.S. 1002, 126 S.Ct. 621, 163 L.Ed.2d 504 (2005). For the purposes of AEDPA, this was the date on which Medley's conviction became final. See Giesberg v. Cockrell, 288 F.3d 268, 271 (5th Cir.2002). Thus, absent tolling, Medley had until November 7, 2006, to file a federal habeas petition. No statutory tolling applied, because Medley did not file a state habeas petition or any other form of collateral attack on his conviction until after the statute of limitations had already expired. See 28 U.S.C. § 2244(d)(2). His instant federal petition, pursuant to 28 U.S.C. § 2254, was mailed by a third party, Medley's mother, from outside the prison system and not filed until March 21, 2007. The district court concluded that it was filed outside of AEDPA's one-year statute of limitations and dismissed the petition.

Medley contended below, and argues on appeal, that because he previously submitted his petition to the prison mail room on October 31, 2006, his petition should be considered timely filed pursuant to the mailbox rule. As we explained in our original panel opinion, “[p]ro se prisoners' filings are governed by the mailbox rule. Thus, they are deemed ‘filed as soon as the pleadings have been deposited into the prison mail system.’ Spotville v. Cain, 149 F.3d 374, 376 (5th Cir.1998) (citing Houston v. Lack, [487 U.S. 266, 108 S.Ct. 2379, 101 L.Ed.2d 245 (1988)] and Cooper v. Brookshire, 70 F.3d 377, 379 (5th Cir.1995)).” Medley, 400 Fed.Appx. at 968; see also Coleman v. Johnson, 184 F.3d 398, 401 (5th Cir.1999) (“Under the ‘mailbox rule,’ a prisoner's federal habeas corpus petition is deemed filed when he delivers the petition to prison officials for mailing to the district court.”).

Medley explained that when he submitted his petition to the prison mail room on October 31, 2006, he concurrently requested that the petition be held pending the deduction of a $5 filing fee from his prison account, so that the fee could be sent with the petition to the district court. The petition was then returned to him on November 4, 2006, with an explanation that the mail room was not permitted to hold the petition pending receipt of the filing fee.

Medley supported his account of these events with signed statements in his brief, as well as two exhibits, which he introduced into the record. The first exhibit, Exhibit A, consists of two pages. The first page is a form, which appears to have been attached by Medley to the materials he initially sent to the prison mail room on October 31. On that form, Medley wrote,

Madam:

Enclosed in the addressed, stamped envelope are documents initiating federal habeas corpus action which require accompaniment of $5.00 filing fee. Also enclosed are two inmate withdrawal slips.

Please process the withdrawal, enclose the $5.00 check with the documents and mail them to the Court using the envelope provided.

Thank you! The second page of Exhibit A, dated October 30, 2006, appears to be associated with the first page, as a cover sheet. It is entitled “Inmate Request to Official” and is addressed to Nancy Jowers, the mail room supervisor for the Clements unit, where Medley was housed. Exhibit B, also dated October 30, 2006, appears to be the accompanying “Inmate Request for Withdrawal.” In it, Medley requests that a $5 withdrawal be made from his prison account and mailed to the “USDISTRICTCOURT.”

Exhibit A also indicates that Medley's submission was rejected by prison staff. The undated “DISPOSITION” of the form in Exhibit A states, “Mail may not be submitted with withdrawal requests. After Unit approval, withdrawals are forwarded to Huntsville for further processing.”

The next two exhibits indicate that after his initial attempt was rejected, Medley continued to inquire about the proper procedure for mailing his petition and filing fee. Exhibit C consists of a form, on which Medley wrote,

Sir,

Filing Federal Habeas Corpus (28 U.S.C. § 2254) requires provision of $5.00 filing fee with the Petition. Please provide the procedure (and time-frame) for taking the $5.00 from my prison account and submitting it with my Petition (to the federal court).

Note: The procedure for releasing money to outside parties (submitting withdraw[al] slip for warden's approval, then to Huntsville, then Huntsville sending a check directly to the party (anywhere from 3 to 6 weeks later)) is inadequate to satisfy the Court's requirements of submitting the filing fee with the Petition in a timely fashion, utilizing the “mailbox” tolling rule/sworn declaration. This request indicates that Medley was, as he explained to the district court and this court, reluctant to resubmit his habeas petition to the mail room and allow it to be mailed separate from his filing fee because he thought that doing so would not be in compliance with Rule 3(a) of the Rules Governing Section 2254 Cases in the District Courts. That rule states that “[a]n original and two copies of the petition must be filed with the clerk and must be accompanied by: (1) the applicable filing fee, or (2) a motion for leave to proceed in forma pauperis ....”

Although the date of Medley's request in Exhibit C is unclear, the disposition of his request is dated January 23, 2007, and states, “[Y]ou need to make out 2 withdrawals to the court provide a stamped addressed envelope to the court or you can have someone from the freeworld to pay the fee. We have no control over how long the check takes to get there.”

Finally, Exhibit D consists of another form, on which Medley wrote,

I intend to file a Petition for Writ of Habeas Corpus in federal court which requires a $5.00 filing fee. May I submit my petition (100 pgs) with my withdrawal request so that it may be mailed to the Court with the check? May I seal the documents? Or ... does the Petition and check need to be mailed to the Court separately? In a response dated August 6, 2007, a prison staff member wrote, “I spoke to law library and they handle these. No, it cannot be sent together. You need to contact them for this particular withdraw[a]l.”

Medley eventually found someone outside of prison, his mother, to mail his petition with his filing fee. They were filed with the district court on March 21, 2007.

The district court adopted the report and recommendation of the magistrate judge in full, and dismissed Medley's petition as being untimely filed. Medley v. Quarterman, No. 2:07–CV–0051, 2008 WL 763075 at *1 (N.D.Tex. Mar. 21, 2008). The district court concluded that Medley was not entitled to the benefit of the mailbox rule for his October 31, 2006 submission, because he “failed to follow proper prison procedure and his mailing was rejected.” Id. at *3. The district court also explained that “to the extent petitioner argues he should be entitled to equitable tolling, in light of his efforts to contact prison authorities and mail his federal petition, such claim is without merit.” Id.

This court granted a certificate of appealability (“COA”) on two issues: (1) whether the district court correctly ruled that Medley was not entitled to the benefit of the mailbox rule, and thus, that his petition was filed outside AEDPA's statute of limitations; and (2) whether, in light of Medley's attempt to file his petition in a timely fashion, Medley was entitled to equitable tolling of the statute of limitations.

In our original opinion in this case, we affirmed the judgment of the district court. We explained that “the mailbox rule ‘[does] not relieve a prisoner of the responsibility of doing all that he or she can reasonably do to ensure that documents are received by the clerk of court in a timely manner.’ Dison v. Whitley, 20 F.3d 185, 187 (5th Cir.1994) (quoting Thompson v. Rasberry, 993 F.2d 513, [515] (5th Cir.1993)) (internal quotation marks omitted).” Medley, 400 Fed.Appx. at 968–69 (first alteration in original). “Accordingly, ‘[f]ailure to stamp or properly address outgoing mail or to follow reasonable prison regulations governing prisoner mail does not constitute compliance with this standard’ and thereby does not entitle one's submission to the benefits of the mailbox rule. [ Dison, 20 F.3d at 187] (quoting Thompson, 993 F.2d at 514) (emphasis removed and internal quotation marks omitted).” Medley, 400 Fed.Appx. at 969 (first alteration in original).

We also explained that the purported mail regulation was reasonable because it “has clear administrative benefits: It relieves the prison of the need to keep track of un-mailed petitions and the responsibility to ensure that the fee is properly submitted with the petition. Therefore, as it does not improperly burden a prisoner's filing of his or her habeas petition, and it serves a positive purpose, the mail regulation is reasonable.” Id. Thus, because Medley had failed to comply with a reasonable mail regulation, we concluded that “the mailbox rule does not apply to Medley's October 31 submission of his habeas petition to his prison mail room. Neither party contests that Medley failed to comply with the prison's regulation for mailing his habeas petition. Therefore, his petition was not accepted by the mail room and was returned to Medley. Contrary to Medley's request that his petition be held so that it could be combined with his filing fee, the regulation required that the petition be mailed separately from the filing fee and mandated that the petition could not be held pending the withdrawal of the fee from Medley's prison account.” Id.

Nor, we concluded, was Medley's concern about complying with Rule 3(a) justified: “Although Rule 3(a) of the Rules Governing Section 2254 Cases in the District Courts states that a petition must be accompanied by the filing fee ... our court has stated that the mailbox rule ‘constitutes an exception’ to Rule 3's requirements; thus a pro se prisoner like Medley need not mail his fee with his petition in order for it be treated as filed.” Id. (citing Cousin v. Lensing, 310 F.3d 843, 847 (5th Cir.2002)).

In his petition for rehearing, Medley asserts that after he submitted his reply brief, he received a response to a grievance, proving that there was no prison regulation requiring him to submit and mail his habeas petition separate from his request that the filing fee be withdrawn and mailed to the court. Thus, he argues, his petition was properly submitted on October 31, 2006, and under the mailbox rule, should be considered filed as of that date. Attached to the petition was a “Step 1 Offender Grievance Form,” which Medley submitted to the prison on December 14, 2009. On the grievance, Medley had written, in relevant part,

It is prison regulation that legal mail may not be submitted and processed with requests for withdrawal from offenders' account to enable the mailing of legal mail with a check.

Federal courts require petition for writ of habeas corpus to be accompanied with a $5 filing fee. See Rules governing 28 U.S.C. § 2254. However, Said Prison Regulation prohibits the mailing of pleadings with withdrawal slips/checks. In response to this grievance, a prison staff member wrote, in relevant part, on the same form,

Your complaint has been investigated and reviewed. Mailroom does not process withdrawals as you state. You send a withdrawal request to the mailroom for court fees. They process the withdrawal and place it in the provided envelope without reviewing the contents. This response is dated as being returned to Medley on January 12, 2010, eight days after Medley's reply brief was filed with this court.

Upon receiving Medley's petition for rehearing, we requested a response from the respondent. In that response, the respondent's counsel of record, a deputy attorney general from the Office of the Attorney General of Texas, explained that an “investigation reveal[ed] that the Clements prison officials do not have any regulation in place that prevents offenders from submitting their court mailing attached to their withdrawal request.” Resp. to Pet. Reh'g at 4. The investigation was conducted by an investigator with the Office of the Attorney General. In an affidavit attached to the response, he states that Nancy Jowers, the Clements Unit Mail Room Supervisor until October 31, 2006, “stated that offenders always were allowed by the Mail Room to mail court filing and fee withdrawal requests together.” The investigator's affidavit also states that Darryl Glenn, the Law Library Supervisor at the time that Medley attempted to mail his habeas petition, “stated that offenders could always submit court filings and fee request [sic] together to the Law Library.” Moreover, all six employees of the Clements Unit whom Clough interviewed stated that they “knew of no such written policy or procedure” which “address[ed] the issue of whether an offender could submit a court filing and a fund withdrawal to be mailed with it or submit a court filing and a fund withdrawal to be mailed separately.”

DISCUSSION

“The decision of a district court to deny a habeas application on procedural grounds is reviewed de novo.” Howland v. Quarterman, 507 F.3d 840, 843 (5th Cir.2007).

We conclude that Medley's October 31, 2006 attempt to mail his habeas petition is entitled to the benefit of the mailbox rule. Although there is an exception to the mailbox rule when a prisoner fails to do “all that he or she can reasonably do to ensure that documents are received by the clerk of court in a timely manner,” Dison, 20 F.3d at 187 (quoting Thompson, 993 F.2d at 515) (internal quotation marks omitted), that exception does not apply here. In view of what we now know—that the purported regulation cited by prison staff in erroneously rejecting Medley's habeas petition does not exist—it is apparent, and the respondent does not contest, that Medley complied with all applicable regulations when he submitted his petition to the prison mail room.

The respondent makes three unavailing arguments for why we should nonetheless affirm the dismissal of Medley's petition as being untimely filed: (1) that Medley waived the argument that the purported mail regulation does not exist; (2) that Medley should not be afforded the benefit of the mailbox rule, because his October 31, 2006 attempt to mail his petition was unsuccessful; and (3) that Medley's claim that he attempted to send his petition on October 31, 2006, is conclusory. We address each argument in turn.

A.

First, we reject the respondent's contention that we should not consider Medley's argument that the purported mail regulation does not exist, because he failed to raise this claim until filing his petition for rehearing. This case is similar to N.L.R.B. v. Robin Am. Corp., 667 F.2d 1170, 1171 (5th Cir.1982), in which we explained that we would consider an argument raised for the first time in a petition for rehearing because there was an “extraordinary circumstance justifying the failure to [raise the argument] until now.” Id. Specifically, the decision below (which this court had affirmed) was “clearly” erroneous in light of an intervening Supreme Court decision, and “[i]t would have been futile, if not frivolous” for the party to raise the argument before the Supreme Court decision was issued. Id.

We conclude that an extraordinary circumstance also exists in the instant appeal. For Medley to have argued previously that the purported mail regulation did not exist would have been futile, if not frivolous. He was hardly in a position to question the representations made by both prison officials and respondent's counsel that the regulation did exist. Indeed, Exhibits C and D of the record show that Medley continued to inquire about the proper procedure for submitting his habeas petition and filing fee, and that prison staff continued to represent to him that the purported regulation existed. Only after Medley had filed his reply brief with this court was he given any hint, apparently by happenstance, that the regulation did not exist.

Additionally, in light of the newly-uncovered fact that the purported mail regulation does not exist, our prior decision was clearly erroneous. Medley complied with all applicable regulations in submitting his petition to the prison mail room on October 31, 2006, and thus is entitled to the benefit of the mailbox rule. And because his submission occurred before the expiration of the one-year statute of limitations, we should have reversed, rather than affirmed, the district court's dismissal of Medley's petition as untimely filed.

Moreover, for us to conclude that Medley has waived this argument would result in a perverse outcome. Namely, it would reward respondent's counsel for failing to investigate and correctly represent his client's policies to Medley, the district court, and this court. This court relied on those representations in issuing our erroneous original opinion. The respondent's current counsel of record, who was also the counsel of record for the respondent's original brief to this court, explains that until we requested a response, he “assum[ed] that facts presented in Medley's exhibits and admissions were as they appeared.” Resp. to Pet. Reh'g 3. Counsel appears to be referring to the responses from prison staff regarding the mail room's purported policy. However, counsel acknowledges that he had no basis to believe that the representations made by those staff were correct, because he “was not familiar with the local practices of the Clements Unit mail room” when he drafted the original brief to this court. Id. We emphasize that in the future, we expect counsel to conduct any necessary investigations in order to ensure that he accurately represents the policies of his client to this court.

B.

Second, we are unpersuaded by the respondent's contention that Medley should not be entitled to the benefit of the mailbox rule because his October 31, 2006 attempt to mail his petition was unsuccessful, and that his subsequent successful attempt to mail his petition occurred after the statute of limitations had expired. That Medley's October 31, 2006 attempt was unsuccessful does not affect the application of the mailbox rule, which applies “ as of the moment [the prisoner's document] is delivered to prison officials for mailing to the [district court] clerk.” Coleman, 184 F.3d at 401 (emphasis added). Here, that moment occurred on October 31, 2006, when Medley delivered his habeas petition to prison staff with a request that they mail it to the district court. That the petition was returned to Medley, through no fault of his own, does not change our conclusion.

Indeed, the logical implication of the requirement that prisoners “follow reasonable prison regulations governing prisoner mail” to receive the benefit of the mailbox rule, Thompson, 993 F.2d at 515, is that the mailbox rule still applies when mail is rejected on an unreasonable ground. Here, prison officials' returning Medley's mail because he failed to comply with a non-existent regulation was unreasonable. The mailbox rule does not require pro se prisoners to compensate for the prison's errors, especially where, as here, it may be impossible for them to even discern such an error. Therefore, the mailbox rule applied to Medley's October 31, 2006 attempt to mail his petition, even though that attempt was not successful.

C.

Third, the respondent erroneously argues that Medley should not be entitled to the benefit of the mailbox rule because his claim that he submitted his habeas petition to the prison mail room on October 31, 2006 is conclusory. As we explained in the background section of this opinion, Medley supported his claim with not only his signed statements in his brief, but also two exhibits, Exhibits A and B, which he introduced into the record. The respondent has not explained why we should doubt the authenticity of those exhibits, or pointed to anything in the record that is inconsistent with Medley's claim.

Notably, the respondent does not suggest what other form of documentation Medley should have provided. Medley does not have the benefit of additional documentation, such as an entry on the prison mail log, because the prison staff wrongly rejected his attempted mailing. To require Medley to provide more documentation, under these circumstances, would reward the Texas Department of Criminal Justice for the misrepresentations made by its prison staff.

CONCLUSION

In sum, we conclude that Medley's October 31, 2006 attempt to mail his habeas petition is entitled to the benefit of the mailbox rule, and thus that his petition was timely filed with the district court. Accordingly, we REVERSE the district court's decision dismissing Medley's petition as untimely filed, and REMAND for further proceedings consistent with this opinion.