It's possible that mod_deflate has been configured incorrectly.
A typical mod_deflate configuration may be excluding certain browsers based on user-agent strings, and may only be configured to compress certain file types - identified by their MIME type as registered on the server.
You should be compressing all of your HTML, CSS and Javascript files, but not your PNG, GIF or JPEG files, and there are bugs with Netscape 4 you may or may not want to account for. Try using the sample code from the documentation:
<Location />
# Insert filter
SetOutputFilter DEFLATE
# Netscape 4.x has some problems...
BrowserMatch ^Mozilla/4 gzip-only-text/html
# Netscape 4.06-4.08 have some more problems
BrowserMatch ^Mozilla/4\.0[678] no-gzip
# MSIE masquerades as Netscape, but it is fine
BrowserMatch \bMSIE !no-gzip !gzip-only-text/html
# Don't compress images
SetEnvIfNoCase Request_URI \
\.(?:gif|jpe?g|png)$ no-gzip dont-vary
# Make sure proxies don't deliver the wrong content
Header append Vary User-Agent env=!dont-vary
</Location>
Note too that the GIDZipTest GZIP test you posted does not test associated Javascript and CSS files, whereas YSlow does - in GIDZipTest GZIP test you'd need to test these individually.
I guess it is also possible that your ISP is using a caching proxy - transparent or not - which is mangling or removing your Accept-Encoding: header. To rule this out as the cause you could get someone to test it from outside of your ISP.
Another thing to note is that when compressing files using gzip you are trading bandwidth for CPU time. Above the lower compression strengths you will see diminishing returns in bandwidth savings, but huge increases in CPU time required. Unfortunately with a compression strength as high as 9, you are almost certainly wasting too much CPU time for very little improved compression - I would always recommend using strength of 1.