Daniel,
Thank you for your guidance--it was very helpful.
I considered your idea of keeping the history of sorts and then replaying them upon a redraw, but that's a bit complicated and it is conceivable that the order of rows could change in response to events other than sorting--the Netflix DVD queue would be an example of that,--and then you'd still have a problem.
What I ended up doing was to persist the sortIndexes returned by getSortInfo. The one tricky part is that redrawing the table resets getSortInfo's frame of reference, so I have to keep around an alias table to translate between the current frame of reference and the original one. I also use getSortInfo's sortColumn and sortAscending in the redraw so as to preserve the visual indicator of the most recent column sorted. As long as the sort algorithm is a stable one, this doesn't cause any problems.
Here's my code with a small test case.
To see the original problem, just comment out the tableDataView.setRows line, and then on the table sort by row number descending, sort by parity, and then click 'redraw'.
If you do make a change to the google visualizations api, I think it would make sense for the draw method to take the entire state returned by getSortInfo as an option instead of just the sortColumn and sortAscending attributes.
David