bloat != corruption. The problem you're dealing with here is a whole lot of dead index entries at the very end of the index range (could be either the lowest or highest entries). The planner is wasting time scanning through those to find the extremal non-dead value for a range estimate. REINDEX got rid of the dead entries; a VACUUM would have done as well.
I completely understand that bloat is different from corruption. It was just really strange that some mass deletes caused this now because we have mass deletes regularly on this DB and it has been running for a few years without any issues. You're right about VACUUM also fixing it, I just tried it inside Docker and after VACUUM finished it instantly fixed the issue. The downside is that VACUUM took a long time to finish.
As noted upthread, more recent PG versions are a bit smarter about such cases.
As far as I understand there is not much we can do except upgrade to future major versions, because on this DB we cannot partition data in that way to be able to drop old partitions.
