Compression schemes have to decode predictably, but they don't necessarily generate the same compressed data. gzip -9 will usually use less space than gzip -1 and decompress to the same data.

What's probably happening is virus scanners are taking the easy way out rather than implementing decompression algorithms in their scanning engines (it probably looks better on traditional benchmarks too)