Paxos is the quintessential example of a highly available, consistent system. It is available as long as more than half of the nodes are up and able to communicate with each other. It remains consistent, regardless of the failure pattern. You really do only have to worry about a true network partition. This isn't a probabilistic argument in any sense.
As you have yourself pointed out, Paxos will in some cases (when less than half the nodes are up) become unavailable, but remain consistent in all cases where it is available.
So it is tolerant of partition and it sacrifices availability in favour of consistency. So it is CP, not CA.
Of course it will become either unavailable or inconsistent (or both) during a network partition. That's the essence of the CAP theorem.
But what does it mean to tolerate a partition? As if the system has a choice?
Any CA system is claiming to be consistent and available as long as the network doesn't partition. That's the strongest statement you can make under the CAP theorem, and Paxos certainly falls in that camp.
My problem with the original article was that it claimed that any individual network or node failure was a partition affecting the consistency or availability of the system. Paxos is a clear counterexample to that, as it tolerates a lot more than that without sacrificing consistency or availability.
Once the network actually partitions (or half the nodes become unreachable), then you are correct. The CAP theorem comes into play again and we must sacrifice either C or A, and Paxos chooses A.
