The headers stored for cached pages ended in a newline, which caused header("") to get called when serving the page.
On some PHP versions (happens on 4.3.3 at least, but not in 5.0), PHP adds a blank header to the HTTP request (i.e. just \r\n) which ends HTTP headers prematurely and adds a newline at the beginning of the page.

This was not an issue before because we output HTML. Now that we have GZip compression, this bug caused corruption of the output. :P
*phew*