What about patents?
gzip was developed as a replacement for compress because of the UNISYS and IBM patents covering the LZW algorithm used by compress.
I have probably spent more time studying data compression patents than actually implementing data compression algorithms. I maintain a list of several hundred patents on lossless data compression algorithms, and I made sure that gzip isn't covered by any of them. In particular, the --fast option of gzip is not as fast it could, precisely to avoid a patented technique.
The first version of the compression algorithm used by gzip appeared in zip 0.9, publicly released on July 11th 1991. So any patent granted after July 11th 1992 cannot threaten gzip because of the prior art, and I have checked all patents granted before this date.
During my search, I found two interesting patents on a process which is mathematically impossible: compression of random data. This is somewhat equivalent to patents on perpetual motion machines. Check here for a short analysis of these two patents.