I should add that it's OK (from the point of view of the RFCs) if gzip produces different outputs given the same inputs when compressing. The RFCs allow that and presumably other gzip implementations do that. All that's required is that compress+decompress result in a copy of the original.
That being said, it's nicer if gzip is deterministic and it'd be helpful to to get to the bottom of this and make the nondeterminism go away in future versions of gzip.
