This may be a naive question, but did they suffer from fragmentation? Reordering tracks via the TOC is a simple operation, but after adding and removing and re-adding songs, I would imagine the writer would need to eventually re-write the entire disc to fragmentation issues, or else have a very complex set of metadata.
I think people would do a disk to disk dub in these situations as a form of "defrag" operation.
You could also get an 80 minute disk, put it in a recorder and get it to read it, then sneakily swap it with a 74 minute disk without letting the recorder's eject switch trip, then force a TOC write, and you would be able to upgrade a 74 minute disk to an 80 minute version.
Statistically though, I imagine reordering to be the most frequent operation. Deletion should be rare since it's a purposeful decision to put the song on the disc in the first place. You might rarely delete one when you get tired of it.