If it's possible for a cat to be alive and dead at the same time, or for a particle to be in two places at the same time, would that show there are at least some things about which one couldn't rely on "Either P or not P" as a sound step in reasoning?

Your question concerns the classical law of excluded middle (LEM): For any proposition P, either P or not P.

Because logic is absolutely fundamental, ceasing to rely on LEM will have ramifications that are both widespread and deep. In classical logic, we can derive LEM from the law of noncontradiction (LNC), so to give up LEM is to give up LNC or the equally obvious laws that allow us to derive LEM from LNC. We should be very reluctant to do that.

In my view, the alleged possibilities that you cite from physics are not enough to overcome that reluctance. First, they are possibilities only according to some, not all, interpretations of quantum mechanics. Second, even if we accept them as possibilities, rejecting LEM or LNC is more costly than (1) reconceiving "being dead" and "being alive" so that they name logically compatible conditions and (2) reconceiving "being here at time t" and "being elsewhere at time t" so that they name logically compatible conditions. It's less costly to mess with the meanings of those phrases than it is to mess with the laws of logic.

Read another response by Stephen Maitzen
Read another response about Physics, Logic