To be precise, the "lossless" compression is still a compression algorithm. They just didn't implement the steps that actually make the compression algorithm lossless.

From the write up:

JBIG2, the image format used in the affected PDFs, usually has lossless and lossy operation modes. Pattern Matching & Substitution„ (PM&S) is one of the standard operation modes for lossy JBIG2, and „Soft Pattern Matching“ (SPM) for lossless JBIG2 (Read here or read the papery by Paul Howard et al.1)). In the JBIG2 standard, the named techniques are called „Symbol Matching“.

PM&S works lossy, SPM lossless. Both operation modes have the basics in common: Images are cut into small segments, which are grouped by similarity. For every group only a representative segment is is saved that gets reused instead of other group members, which may cause character substitution. Different to PM&S, SPM corrects such errors by additionally saving difference images containing the differences of the reused symbols in comparison to the original image. This correction step seems to have been left out by Xerox.