I had in mind to rule out your "practical agnosticism" with the polynomial time condition.

That is a reasonable assumption to make. We just need to explicitly assert that the intelligence is willing and able to return P(A) for any sane length A that matches the polynomial time condition. (And so explicitly rule out intelligences that just compute perfect answers and to hell with polynomial time limits and pesky things like physical possibility.)

If we're going to allow explicit agnosticism, we're going to have to rethink some things. If P(A) = refuse to answer, what are P(B|A) and P(A|B)? How are we supposed to update?

I don't know and the intelligence doesn't care. It just isn't going to give you wrong answers. I think it is reasonable for us to just exclude such intelligences because they are practically useless. I'll include the same caveat that you mentioned earlier - maybe there is some algorithm that never violates logical consistency conditions somehow. That algorithm would be an extremely valuable discovery but one I suspect could be proven impossible. The maths for making such a proof is beyond me.