"diffing the entire virtual DOM for every update is basically free in comparison"
If you use something like Immutable.js you can avoid a lot (most? all?) of the diffing since comparing trees of objects becomes a simple object reference comparison. This is common in the Om world, and becoming more popular in JS too.
If you have a complicated, deeply interconnected model, updating immutable data structures properly doesn't seem much easier than properly implementing shouldComponentUpdate().
You could use a lens to make the programming easier, and the logarithmic depth property of DOM-like trees makes it likely that allocation will also not be a problem.
Is it not easy because the syntax is cumbersome (eg. chained calls to setIn([...]) in immutable.js), or because it is fundamentally difficult? The former is something that's specific to Immutable.js and many other javascript frameworks. Other languages have solved that problem rather elegantly (cursors, lenses). If it's the later then I doubt shouldComponentUpdate will be much less complex than the state update function (in terms of complexity, lines of code, easy of understanding etc).
If you use something like Immutable.js you can avoid a lot (most? all?) of the diffing since comparing trees of objects becomes a simple object reference comparison. This is common in the Om world, and becoming more popular in JS too.