My interpretation of this is that the indexing system was resilient to lost of a certain amount of capacity (probably around ⅓ + 1 host). As a guess, the indexing system probably used some form of consensus (e.g. paxos) which has had an active leader for years. Deployments stay within that capacity constraint, so while hosts have been restarted and replaced (data center migrations, hardware lease expiration, failures, upgrades, etc.), they may have not recently run into a situation where quorum wasn't available for a partition, especially at the scale of restarting the entire fleet.
Since restarting the entire fleet would incur downtime of all relevant S3 operations, it's unlikely that it was something ever intentionally done in production (and they may or may not have run that scenario in other environments).
Source: I used to run several large scale services at Amazon.