Actually, according to your own blog post on the subject, Gilbert and Lynch define a partition tolerance as:
“The network will be allowed to lose arbitrarily many messages sent from one node to another”
There's a huge world of difference between the network losing arbitrarily many messages, and the definition you use elsewhere in this thread: namely, any subset of packets dropped, no matter how small, counts as a network partition.
No, arbitrarily many doesn't automatically mean a huge amount :) This definition covers permanent partitions, but also encompasses temporary partitions which are effectively one dropped message or more. There exist protocols which will be broken by the loss of a single message. Paxos may not be one of them, but there is also a pattern of loss which will break that as well.
The theory behind all this really does hold this point up. I have another blog post with much more detail on the theory here: http://the-paper-trail.org/blog/?p=49, but I warn you it may be heavy going.