I first became interested in CRDTs in a case where this wasn't really true. I was writing an IDE for a custom in-house DSL - think of the application as a special language for interacting with a gigantic and very strange database. Basically, the problem was that the use case really stretched the bounds of what is normally done with syntax highlighting. Some requirements:
- It had syntax and semantic highlighting, where the visual feedback associated with a term would depend on the results of queries to the remote database
- It had to be able to handle documents of several megabytes (and many thousands of terms) fairly smoothly, with as little noticeable lag or flicker as possible
- It couldn't swamp the database with unnecessary requests
- The document itself had implicit procedural state (e.g. if you wrote a command that, if evaluated, would alter the state of a term on the database, appearances of that term later in the document needed to be highlighted as if those changes had already been applied)
So I definitely couldn't throw out metadata and start over with every change. I ended up with a kind of algebraic editing model that allowed me to put bounds on what needed to be updated with every edit and calculate a minimal set of state changes to flow forward. It was extraordinarily complicated. I never got around to learning enough about CRDTs to determine if they'd be simpler than the solution I came up with, but they do seem to target some similar issues.