While running some errands, I think I realized the core of my trouble accepting this proof. I think it may be the same for a lot of people, but I've never heard it stated, so here it is:
To my mind, it seems logical that if P reaches a paradox, it never returns. It's an infinite logical loop, never finishing, thus never returning true or false. Like evaluating "this statement is false", it's stuck on "if it's true, it's false. If false, true". To that end, the paradox isn't a paradox: it just never finishes.
If this is the case, then P(Q(Q)) does indeed escape the problem entirely: it shows that Q(Q) will never finish. That argument I've made, and I've seen others make, but the realization of the previous paragraph is new. And nobody I've debated this with has really attempted to look outside of "but it's a proof, it proves it", and re-iterating the steps of the proof. Not that many have tried for very long, they usually get upset that I can't see the "obvious". Thanks for sticking it out, I've had longer to think on this than I've had with others, and that may have been what I needed.
This reveals a missing assumption in the proof, or at least one I've never seen stated: that P must finish. If it must finish, then I accept the proof completely. If it's a paradox, I agree, it's a paradox, and it certainly is within that requirement. It must return, but it cannot, therefore it can not exist.
But then I must ask: Why must P finish on all inputs? I can make a program which doesn't (print(num) when passed Pi), why not this one?
I'd be very interested in any input / rebuttals to this. I'm not trying to be difficult, honest! I've understood the proof where P must finish for quite a while, but I don't see that it's a valid assumption if categorically stating that it's inherently un-doable.