Why not have a database for each user? Evernote's data is partitioned perfectly for that. Notebooks and notes are accessible to one user or are public. There is no sharing notes between users.
Actually, his idea of a database for each user could still work, even though there is sharing of data between users. Take each database, and turn it into an executable object, which reads/writes its own data, and which communicates with other objects for sharing. It's like taking the actor model of computation, and orienting it for database use. I don't know of any working example of where this has been done, but I don't see why it wouldn't be feasible.