For those not believing these things happen with any frequency, I'll add another data point to the mix. Our 2013 P85 (bought in 2015 when they started the CPO program) currently has 244k miles on it. The battery has been replaced twice, once at 190k and again at ~220k. The first time was because the car would basically say we were out of juice and shut off, yet the gauge still showed 40+ miles of range.
When was that battery replaced the first time? (It is likely that Tesla has recently resolved the early shutdown problem with firmware updates, so that particular issue might not happen anymore.)