ECDH Public Key Recovery - Determine if valid key exists from just signature and message
"My question is if there is a fast way of determining whether P exists, without doing the full expensive calculations to determine P."

I believe that you could check whether $r$ is a valid nonzero $x$ coordinate; that is, whether it is a part of a solution to curve equation (e.g. if your curve is in Weierstrass form with characteristic > 3, you'd check whether $x^3 + ax + b$ is a Quadratic Residue).

If it is (and if it is nonzero), then yes, you could perform the operations to recover $P$, and it would come up with two valid points, and so that's your answer.