I'm not sure I would characterize it that way. Even with immutable data you can be uncertain whether a value is stored on a system on the other side of a partition. You're only confident that if you can see the data, it hasn't changed somewhere else (which, don't get me wrong, is a tremendously valuable property).
when you define things in terms of immutable structures, the worst thing that happens is you get an _old_ answer - but not an incorrect one. the old answer comes back with a timestamp: "this is the answer to your question, as of (time)"
the CAP theorem means you either give _inconsistent_ answers (what is the state now? it's X) to two different nodes, or you sacrifice availability.
this is the paper in which the theorem was formalized. they talk in terms of 'the initial value' of an atomic object, and its 'subsequent values' - so this only makes sense when the system is _implemented_ in terms of objects which have values that change over time as the result of operations:
---
More formally, let v0 be the initial value of the atomic object. Let c~1 be the prefix of an
execution of A in which a single write of a value not equal to v0 occurs in G1, e
---
If requests that come in are expressed as "give me the most recent value of A," and the response comes back with a history of all operations done on A along with timestamps, then you're no longer bound by the CAP theorem because 'an operation was missing' is no longer a _problem_ - its' just an outdated answer.
yes, i'm saying that the cap theorem only applies when you have a shared state storing mutable objects which change over time. if there is an append-only record, the CAP theorem - as formalized here (http://dl.acm.org/citation.cfm?id=564601) - doesn't apply