Det är inget som jag haft problem med heller, men folk har postat diverse bugrapporter till PHPs bugsystem som beskriver exakt problemet som drabbar dina besökare. Rapporterna blir dock prompt klassade som "bogus" för att det är ett problem med IE. Läs t.ex.
http://bugs.php.net/bug.php?id=38026 . Så det är kanske värt att prova att slå av komprimeringen helt och hållet eller kanske testa att låta apache sköta det hela via mod_deflate.