http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.20.1...
CAP is absolutely not a paradox; it is just a conjecture or a theorem.
As far as CAP and distributed databases, it is worth noting that a lot of distributed DBs don't actually need to be partition-tolerant.
Amazon Dynamo (and various open source datastores which borrow its infrastructure- Voldemort, Dynomite, Cassandra) is a classical example of a partition tolerant datastore: rather than using two phase commit at write time (meaning writes could fail if the cohorts and the coordinator are separated) it uses vector clocks for read-time reconciliation.
OTOH, saying partition-tolerance is unimportant is only partially-true if your db is only going to run on a single lan. This is often the case (i.e. basically saying that "distributed" is another word for "cluster") but if your db is going to run across a wan then sacrificing partition-tolerance can have unpleasant consequences. I do a lot of work in Erlang and its built-in distributed db (like the language itself) was designed to run in a phone switch among SBCs and blades that shared a common backplane. In this case a partition meant that something extremely bad was happening and graceful shutdown/failure in the face of a partition was a good choice. Now that a lot of us are using these tools out in the wilds of the internet we are discovering that sacrificing partition-tolerance has some unpleasant side-effects too: running mnesia across EC2 instances, for example, is not a trivial undertaking because you need to deal with inevitable network problems by shutting down auto-rejoin features of the db and effectively turn off availability for a short period during the rejoin.