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.
