Steps to reproduce:
1. Clear your cache in admin > performance
2. wget --header="accept-encoding: gzip" http://your-drupal-website/page
3. Observe that the file is not a binary gzip
4. Do it again (wget....)
3. Observe that the new file *is* a binary gzip
This is more of a design problem:
line 573 of bootstrap.inc, latest D6 you notice that
ob_start() is called if cache is empty.
1620 of common.inc, the cache is finally set, for the next time -- because for this particular render, the ob_start takes care of things.
Current stop-gap solution:
line 573 of bootstrap.inc to
ob_start("ob_gzhandler"); which assumes you have zlib installed and working.