Consider US Patent #5533051:
To my best understanding, what the patented algorithm says is that it can guarantee a lossless one-bit compression on any input. Clearly this is totally impossible (recursivly apply the algorithm to reach a one-bit representation of any input).
Am I understanding this algorithm the wrong way?
Your understanding is correct. The algorithm as described will loop forever for some inputs (since the answer to "is the output file at or below required size?" will always be "no").
See the comp.compression FAQ for an in-depth discussion of claims of being able to compress any input and compression of random input.
The patent presents three encoding methods, as well as an algorithm for selecting a minimum-size compression from a set of compression routines. I assume you are talking about the algorithm in sheet 2, which is intended to select the best result from a set of routines.
The algorithm will loop through three routines as long as the "required size" is below the size it is able to compress the text down to. If it can't compress below the required size using any of the routines, it uses a "routine for highly randomized data".
And there's the flaw; it checks the size requirement again, and then resets if the size is above the required size. Hence, it will loop forever for some inputs. I am pretty sure the final decision on size is not supposed to be there, and that the final routine is supposed to act as a fallback.
I cannot find any claim in the patent like the one you state, although there is a bug there that will make the algorithm loop.