WOOD, Circuit Judge.

Blake Conyers, an Illinois prisoner, filed suit under 42 U.S.C. § 1983 against Wisconsin prison officials for actions taken while he was incarcerated in that state. The district court granted summary judgment to the defendants, reasoning that Conyers had failed to exhaust his claims. We conclude, however, that Conyers did exhaust one of his claims and so remand in part for further proceedings.

The incidents giving rise to Conyers’s complaint began in 1995. In May of that year, guards searched Conyers and confiscated gang-related photographs he had on his person. Conyers was punished, but his disciplinary conviction later was expunged after a successful administrative appeal. Next, in October 1995, guards frisked Co-nyers as he was leaving the prison chapel. The search revealed no contraband, though Conyers received a disciplinary ticket for behaving disruptively during the search. Conyers was found guilty at a disciplinary hearing; this time his appeal of the conviction was unsuccessful. Then, in December 1995, guards confiscated more prohibited photographs and other materials from Conyers’s cell and wrote him a disciplinary ticket. The ticket was classified as a major offense because Co-nyers had previously been convicted of possessing the same typ.e of contraband, even though that conviction had been ordered expunged. A few days later Co-nyers was sentenced to 90 days in segregation; the prison officials affirmed his disciplinary conviction on appeal.

On January 20, 1996, while Conyers was serving his segregation time, he asked to be provided with late bagged dinners during the Fast of Ramadan but was told that the deadline to sign up for that service had passed. During the month-long period of Ramadan, Muslims abstain from eating between dawn and dusk. Ramadan does not occur during a specific month or season; its timing is based on the lunar calendar and the start date moves backwards by eleven days each year. In 1996 Ramadan began on January 22. Although the sign-up deadline, January 16, had been posted in the prison’s daily bulletin, Conyers did *583 not have access to that bulletin while in segregation. On February 12, 1996, he was released from segregation. On July 22, 1996, Conyers filed a prison grievance, complaining that because he did not have access to the daily bulletin in segregation and thus was unaware of the sign-up deadline, he had been denied the ability to participate in the Fast of Ramadan.

The prison’s grievance examiner recommended that the warden dismiss Conyers’s grievance, reasoning that Department of Corrections procedures do not mandate providing bulletins to inmates in segregation at Conyers’s prison, and that he should have contacted the prison chaplain immediately upon placement in segregation to ensure his meal accommodation. The examiner also “reminded” Conyers that grievances should be submitted within 14 calendar days after the occurrence giving rise to the complaint. The warden, after receiving the examiner’s report, dismissed Conyers’s grievance without further explanation. Conyers appealed the dismissal to the Secretary of the Department of Corrections, and a different examiner recommended dismissal based on the original examiner’s report “and also considering the untimeliness of the original complaint.” The Secretary, the final reviewing authority, “accepted” that recommendation.

In October 2001, Conyers filed this action claiming constitutional and state-law violations. At the initial screening, see 28 U.S.C. § 1915A, the district court concluded that any claims arising out of the May 1995 search were barred by the applicable six-year statute of limitations for § 1983 claims arising in Wisconsin, see Wudtke v. Davel, 128 F.3d 1057, 1061 (7th Cir.1997). Later, in response to a motion from the defendants, the court also dismissed Co-nyers’s claim that the discipline imposed after the December 1995 search of his cell violated his right to due process, reasoning that Conyers may have had a protected liberty interest affected by the discipline, but, because the officers’ conduct was random and unauthorized and the post-deprivation procedures available under Wisconsin law were adequate, there was no due process violation. The court declined to dismiss Conyers’s Fourth Amendment claim concerning the October 1995 search or his claim that the defendants violated his right to religious exercise by hindering his observance of the Fast of Ramadan.

In June 2003, after the district court’s ruling, Conyers moved to amend his complaint, ostensibly to add additional state-law claims. Primarily, though, his motion argued that the court should have inferred a claim for retaliation from his original complaint and that the court overlooked other federal and supplemental state-law claims implicit in his original complaint. The district court denied leave to amend, reasoning that Conyers had no excuse for waiting 20 months to file his motion, and that allowing the amendment would unduly delay the action and prejudice the defendants. The court did not respond to Co-nyers’s contention that some of his claims had not been addressed.

The defendants ultimately moved for summary judgment on the frisk and religious-exercise claims that survived screening and their motion to dismiss. They argued that Conyers had failed to exhaust his administrative remedies with respect to these claims because he filed no grievance concerning the frisk and his grievance about the Fast of Ramadan was deemed untimely. The district court agreed with this position and dismissed the suit in its entirety. On appeal, Conyers challenges the district court’s conclusion that he failed to exhaust his administrative remedies for the October 1995 search and the Fast of Ramadan in 1996. Conyers .also argues *584 that the court did not analyze all of the claims in his original complaint.

An inmate complaining about prison conditions must exhaust administrative remedies before filing suit. 42 U.S.C. § 1997e(a); see Porter v. Nussle, 534 U.S. 516, 524, 122 S.Ct. 983, 152 L.Ed.2d 12 (2002). Exhaustion requires complying with the rules applicable to the grievance process at the inmate’s institution, Pozo v. McCaughtry, 286 F.3d 1022, 1025 (7th Cir.2002). Under Wis. Admin. Code § 310.09(6), a grievance must be filed “within 14 calendar days after the occurrence giving rise to the complaint” unless accepted late “for good cause.” Failure to comply with administrative deadlines dooms the claim except where the institution treats the filing as timely and resolves it on the merits. Riccardo v. Rausch, 375 F.3d 521, 524 (7th Cir.2004). In that instance the grievance has served its function of inviting prison administrators to take corrective action, and thus the administrative exhaustion requirement has been satisfied. Id.; Pozo, 286 F.3d at 1025. Failure to exhaust administrative remedies is an affirmative defense that must be established by the defendants, Dale v. Lappin, 376 F.3d 652, 655 (7th Cir.2004). We review de novo the question whether the prisoner has met the exhaustion requirement. McCoy v. Gilbert, 270 F.3d 503, 508 (7th Cir.2001).

We have no difficulty upholding the dismissal of Conyers’s claim about the October 1995 frisk that occurred outside the prison chapel. Conyers concedes that he did not even try to file a grievance concerning that search. He argues instead that his administrative appeals from the resulting disciplinary conviction should be deemed an adequate substitute. Even if disciplinary administrative appeals can satisfy the exhaustion rule of § 1997e(a), see Giano v. Goord, 380 F.3d 670, 679 (2d Cir.2004) (disciplinary appeal may be sufficient to exhaust in certain circumstances), there would be no point in allowing the Fourth Amendment claim to proceed because it is frivolous. The defendants produced evidence that they have a legitimate security interest in frisking inmates as they leave the prison chapel because the chapel is a hotbed of contraband exchange. We generally defer to the judgment of prison officials when they are evaluating what is necessary to preserve institutional order and discipline, and it is unreasonable to suggest that Conyers retains a privacy interest in not being frisked that could suffice to overcome that deference. See Bell v. Wolfish, 441 U.S. 520, 547-48, 99 S.Ct. 1861, 60 L.Ed.2d 447 (1979).

The Fast of Ramadan claim is significantly different. The district court, at the defendants’ urging, concluded that prison administrators dismissed Conyers’s grievance as untimely, but the record does not support that conclusion. At the initial stage of review, the warden offered no explanation for dismissing the grievance, and so we must assume that the warden acted on the basis of the initial examiner’s recommendation. That examiner’s report included a “reminder” to Conyers to follow the timing rules but otherwise rejected the grievance on the merits. Likewise, at the second and final level of review, the Secretary of the Department of Corrections accepted the recommendation of a different reviewer to dismiss on the basis of the first examiner’s report “and also considering the untimeliness of the original complaint.”

We have held that a prison grievance rejected solely on the basis of untimeliness will not fulfill the exhaustion requirement. Pozo, 286 F.3d at 1025. We have also explained, however, that if prison administrators choose to consider the merits of an untimely grievance, then the claim has been exhausted. Riccardo, 375 F.3d at 524. Conyers asserts at one point that *585 his grievance was decided on “dual” grounds; elsewhere he argues that he substantially complied with the exhaustion requirement for a variety of reasons. Although the defendants argued in district court that the grievance was dismissed as untimely, they now adopt the view that it was dismissed for both untimeliness and lack of merit. In such a ease, they urge, the grievance was not properly filed. That may be true if the record makes it clear that there were two independent grounds for the decision, but a procedural shortcoming like failing to follow the prison’s time deadlines amounts to a failure to exhaust only if prison administrators explicitly relied on that shortcoming. See Ford v. Johnson, 362 F.3d 395, 397-98 (7th Cir.2004). This record reveals that the grievance was principally rejected on the merits with an ambiguous secondary observation that it was untimely. We conclude that Conyers has exhausted his administrative remedies as to his Fast of Ramadan claim.

The defendants argue in the alternative that the dismissal is sustainable on other grounds. Primarily, they contend that they had a sufficient reason to ignore Conyers's request to participate in the fast, but their summary judgment evidence is too poorly developed to support a decision in their favor. Under the First Amendment, prisoners retain a right to free exercise of religion, although that right is subject to legitimate penological demands of the state, Tarpley v. Allen County, Ind., 312 F.3d 895, 898 (7th Cir.2002). Compare Cutter v. Wilkinson, U.S. —, 125 S.Ct. 2113, 161 L.Ed.2d 1020 (2005) (upholding Religious Land Use and Institutionalized Persons Act of 2000, 42 U.S.C. § 2000cc-l(a)(l)-(2), which requires prison officials to accommodate inmate religious practices absent compelling interest otherwise). The defendants offered the general explanation that they imposed the sign-up deadline to give the prison’s food-service and segregation unit time to prepare and coordinate meal accommodation.

The defendants also claim that they cannot be blamed for Conyers’s failure to anticipate Ramadan in time to contact the chaplain on his own before the deadline. But they offered no evidence to explain the additional effort that would have been required to include Conyers in the fast. They rest instead on the rigid and unsupported assumption that a sign-up deadline like the one imposed is a reasonable administrative requirement under any circumstances. See Freeman v. Arpaio, 125 F.3d 732, 737 (9th Cir.1997) (requiring sign-in sheets for participation in religious activities was not a substantial burden on free exercise). Nothing in this record indicates that convenience and notice to prison staff justified the rejection of Conyers’s request to participate in the fast, especially since he missed the notification deadline by just four days and in fact alerted the defendants that he desired to participate in the Fast of Ramadan two days before it began. It is notable in this connection that the prison was willing to accommodate Muslims transferred from other institutions after the notification deadline. See Makin v. Colo. Dep’t of Corr., 183 F.3d 1205, 1213-14 (10th Cir.1999) (holding that staff availability and proper allocation of resources were not sufficient reasons for refusing to permit Muslim inmates confined in segregation to participate in Fast of Ramadan); Love v. Reed, 216 F.3d 682, 690-91 (8th Cir.2000) (sanitary concerns and potential inmate discontent over providing another inmate with food to prepare and consume on the Sabbath were not sufficient penological interests); compare Williams v. Morton, 343 F.3d 212, 220-21 (3d Cir.2003) (simplified food service, security, and budgetary concerns are legitimate penological interests justifying substitution of vegetarian meals for Halal meals with meat).

*586 The defendants also urge ■ us to affirm on the basis of qualified immunity; in their view, they “could not have been expected to know that not providing [Co-nyers] with advance written notice of the sign-up deadline would violate his freedom of religion.” But this formulation misapprehends the nature of Conyers’s free-exercise claim. The defendants argue only that Conyers was responsible for contacting the prison chaplain, but they present no evidence that Conyers knew that there was a sign-up deadline. They have tried all along to fault him for not realizing on his own that Ramadan was approaching. But, of course, he did realize that Ramadan was about to start, and he asked to participate in the fast before it commenced. The relevant inquiry is whether, at the time the defendants refused Co-nyers’s request, the law was clearly established that prison officials must have a legitimate penological interest before imposing a substantial burden on the free exercise of an inmate’s religion, even when that inmate is in disciplinary segregation. We have held, in the specific context of Muslim inmates who were denied pork-free meals while confined in disciplinary segregation, that prison officials must demonstrate a legitimate penological objective for decisions that impede religious exercise. Hunafa v. Murphy, 907 F.2d 46, 47 (7th Cir.1990); see also McEachin v. McGuinnis, 357 F.3d 197, 204 (2d Cir.2003) (free exercise is violated when generally applicable prison policies fail to accommodate segregated inmate’s religious dietary requirements). So that brings us back to the defendants’ asserted interest and the insubstantial evidence they offered to support it.

Conyers next argues that the district court erred in denying him leave to amend; we review for an abuse of discretion. Dubicz v. Commonwealth Edison Co., 377 F.3d 787, 792 (7th Cir.2004). Conyers filed his original complaint in October 2001 and his motion to amend nearly two years later. Given this delay and the fact that Conyers sought to amend in large part only to alert the district court that it had “mistakenly or inadvertently” failed to address everything in his original complaint, we see no abuse of discretion in the district court’s conclusion that allowing amendment would unduly delay the litigation and prejudice the defendants.

Nor do we agree with Conyers that the district court failed to address other claims in his complaint. Conyers says that the complaint includes other “Equal Protection and Eighth Amendment claims” related to his Fast of Ramadan claim, but the free-exercise claim arises under the First Amendment and gains nothing by attracting additional constitutional labels. See Graham v. Connor, 490 U.S. 386, 395, 109 S.Ct. 1865, 104 L.Ed.2d 443 (1989) (constitutional claims must be addressed under the most applicable provision). Conyers also seems to interpret his complaint to include a claim that prison officials conspired to deny him access to administrative review of his grievances by dismissing them. If that is what he means, his argument is frivolous. Conyers' had access to the grievance procedure; he simply did not obtain the outcome he desired. Finally, Conyers contends that the district court never addressed his state-law claims. Presumably, the district court declined to exercise its supplemental jurisdiction after dismissing Conyers’s federal claims, and although we have difficulty discerning the exact nature of those state-law claims, we leave it to the district court to address them on remand.

Accordingly, the judgment of the district court is AfpiRmed in part, VaCated and Remanded in part.