If Baidu served everything over https, would that effectively make this attack impossible unless the China GFW mitm'd the connections? I suppose that might add a significant server load to Baidu, but I wonder if we should just start accepting SSL as a cost of doing business on the internet.

Of course, that would require Baidu's cooperation, and I suppose they might now want to raise the ire of the Chinese government. Also, I suppose the government could just use their own heavily trafficked sites to do this, but that should isolate it somewhat to Chinese IP ranges.