Paper #1: accepted. Two different PC members sent questions: one concerned a possible simplification of our results (which I think overlooked some of the difficulties of the problem) while the other asked for more motivation for some of the results. I was a little worried at this point, because my general feeling was that any questioning implied something other than a slam-dunk accept by the committee, but it was accepted after all. And in the author feedback, the committee specifically thanked us for what they saw as helpful answers. Verdict: rebuttal probably helped here.
Paper #2: rejected. The PC "question" basically consisted of a long negative review to which little response was possible. It was obvious that, if the PC member sending this comment was representative of the rest of the committee, then the paper would be rejected. Nevertheless we made some attempt at response. The author feedback acknowledged that we did so but to my mind didn't show any evidence that we'd made any difference. (However, one of my co-authors disagrees, writing "It looks like we made up some ground with the rebuttal, but not enough.") Verdict: It was probably a slight plus to have the committee's decision telegraphed early in this way, in that it softened the blow of the later real rejection, but otherwise rebuttal was a pointless waste of time.
Paper #3: rejected. The PC did not submit any questions and the author feedback made it clear that they understood the paper well enough and just weren't sufficiently excited by it. Rebuttal would not likely have helped. Verdict: A good choice by the committee not to waste anyone's time with rebuttal.
Paper #4: rejected. The PC did not submit any questions. The author feedback contains some inaccuracies that probably hurt this paper (e.g. a description of the submission as an improvement to some other work that was actually subsequent) but it also makes it clear that all the reviewers on the PC found this paper confusing in many ways. Rebuttal could probably have helped a little, but not enough to tip the balance in favor of this paper. Verdict: because rebuttal was not used, it failed to prevent the sort of error it was intended to prevent, in which the PC made a decision based in part on an easily-corrected mistake. But the much bigger failure was from the SODA program committee, whose author feedback from an earlier rejection did not give me any idea just how confusing this paper would be to the SoCG committee. Instead I got the impression that I could just resubmit without serious revision, and that seems to have been the main factor behind the rejection this time.
In general, I think the cost of doing rebuttal is not so high, so that if it makes a few improvements to the committee's decisions then it's probably worth it. And that's especially true when (as in cases #3 and #4, and unlike case #2) the committee avoids using rebuttal when it can be predicted to be pointless. So, based on the possibility that rebuttal may have helped in case #1, I think having a rebuttal phase was a good idea.
I would be very interested to hear more from the committee, though, whether they thought it was helpful, since they have a bigger perspective on a larger set of papers. For instance, what fraction of papers had their scores changed in any significant way by the rebuttal phase? Perhaps we can hear more from the chair at the conference business meeting, using aggregate statistics that don't compromise the confidentiality of any particular submissions?
PS Suresh has a related post praising the SoCG committee for the high quality of their reviews. It's tangential to the point of this post, but I completely agree. He also posts his rebuttal experiences which seem similar to my cases #2 and #3.