Very interesting analogy. Many 3D modeling programs had undos based on clean abstractions (history of transformation matrices for object P/O/S, stack of operators to influence geometry) but it often broke when you go below. Houdini (one that was fairly dogmatic about being 'procedural') had to reify vertices/edges modification as an Edit node in its object graph to stay coherent without losing information (or making it a second class citizen).
There is an [episode of vimcasts](http://vimcasts.org/episodes/modal-editing-undo-redo-and-rep...) which compares editing in vim's insert mode to making a brush stroke in a graphics program. With this plugin one must be careful not to make the brush strokes too long.