Get rid of 2-column format, and generally streamline paper preparation
Right now the typical TCS paper has 4 different versions:
1) A preliminary full version - this is the version with full proofs you work on before the conference submission, and the one many people post online around the same time as submission.
2) A submission version - this is a version, hastily prepared a couple of days before the deadline, where we convert a nice 30 page paper into a less readable 10 page paper + 20 page appendix by copy/pasting proofs into appendices.
3) Camera-ready version - this is the version in the two column format that actually gets published in the conference. This is obtained by incorporating reviewer feedback and insights we obtained in the meantime into the submission or preliminary full version, and then working to make it compatible with the ugly 2-column format template provided by the conference. (I think there's more or less universal agreement that the 2-column format is ugly, and the only reason it exists is as a remnant from the not so long ago days of printed proceedings.)
4) Journal version - this is a full version that also contains the above feedback and insights, as well as the result of another pass that we submit to a journal. For technical reasons, it's often hard to maintain the same tex file for versions 3 and 4, which means that one needs to duplicate the work in creating these two versions.
Given this, perhaps it's not surprising that many papers don't make it to stage 4, and the most mature version that remains is this ugly 2-column format.
I'd suggest the following changes:
1) As Emanuelle said, submit a full preliminary paper (i.e., version 1) to the conference, with the understanding that the PC is not obligated to read beyond the first 10 pages, and that they generally can use their judgment to skip technical details of the proofs.
This makes it easier for the authors (one less version) and also for the PC, since if they actually want to see the proofs, they don't have to hunt for them in the appendices, and they can always simulate the current situation by just printing the first 10 pages of the submission and ignoring the rest. (Russell Impagliazzo once said that a submission should have no page limit, but just an instruction that for x=1,2,4,8,... reading the first x pages should make the reviewer want to read the next x ones.)
2) For the camera-ready version, use a 1-column format with a minimally intrusive latex template, that will make it easier to keep working with the same file.
In fact, what I would suggest (though it's a bigger change) is to make the camera-ready version a true "extended abstract" by restricting it to 10 pages of single column. Given that your paper is already accepted, and that a version with the full details should be available online, you don't have to waste space in these 10 pages on explaining more details or enumerating all arguments why your paper is great, and you can focus on trying to explain in the simplest possible way the main ideas behind your work. I think a paper in this format will actually be a valuable resource and will justify having one more version on top of the full/journal version. Also, I think the fact that the conference version will be necessarily be without proof details will encourage people to submit to journals.