It compresses the plumbing, not the pictures
A PDF is a pile of numbered objects: page descriptions, fonts, image data, and the table that says where each one sits. This tool reads yours, packs those objects together, and writes the file out again. Your pages, text and images come through unchanged, because none of them are re-encoded.
Why one PDF loses half its size and the next loses nothing
The saving comes from a feature the PDF standard calls an object stream. ISO 32000-1:2008 describes it as “a stream object in which a sequence of indirect objects may be stored”, and says its purpose “is to allow indirect objects other than streams to be stored more compactly by using the facilities provided by stream compression filters” (7.5.7). A companion table of contents for the file, the cross-reference stream, can be packed the same way (7.5.8).
Read the words “other than streams” carefully, because they decide the whole result. The same section lists what may not go into an object stream, and the first item is stream objects. Pictures are stored that way: the standard says an image XObject “is a stream object whose dictionary specifies attributes of the image and whose data contains the image samples” (8.9.1, NOTE 2). Page contents and embedded fonts are streams too.
So the method packs the file's structure and leaves every stream, pictures included, as it was. A document built up over many rounds of edits carries a lot of structure and little else, and can lose a noticeable share of its size. A scan is almost entirely image data, so there is very little left for this to pack — and that is the real reason it hardly moves, not a fault in the file.