Jim Battle wrote a good description of compression eliminating redundancy,
and mentioned:
Even though G4 compression is 2x as effective as G3
compression (on
bilevel images), fax machines still use G3 because any error propagates
to the end of the scan line whereas the same error in a G4 file can
trash the image all the way to the end of the page.
I'd point out that G4 compression was specifically designed for use over
an error-corrected ISDN link, where that would not be a problem. In
principle G4 compression would work fine on dialup if V.42 error control
were used. But as you say, all commmon fax machines stick to G3.
Eric