The slowness of my example from the other day seems to be caused by the fact that each top-level output record (of which there are 1000 in my example) is moved individually, and moving an output record triggers a call to recompute-extent-for-changed-child. The parent then scans all the children to compute the new bounding rectangle, resulting in quadratic behavior.
The solution to this problem seems to be to realize that incremental redisplay must traverse all the output records anyway (to see what has changed), and so it would be a better idea to put off the computation of the bounding rectangle until the end of this entire process.
I maintain my previous analysis that it would be a better idea to store relative positions in output records, so that moving an output record does not require traversing its children.