I don't think you'd absolutely need ubiquitous internet access if the underlying "cloud" was based on a network filesystem that supported disconnected operation. So some files would be synced/cached locally. And then when you went off-network you'd still have access to (some of) them.
that still doesn't solve the problems of different devices having different capacities.
For example, my entire music collection is ~100GB (on my file server at home). On my laptop, I can afford to devote ~40GB to music, and on my iPod I can get ~30GB. The only way I can think of to solve this sort of problem (i.e., guarantee that I always have access to the song I'm looking for) is to have network access. And then I get 'synchronization' for free since all my data is in one place anyways.
