First of all, compression doesn't have to be limited to just commonly occuring sets. For example, if I create a fractal, you don't have to find out commonly used colors or pixels that occur near each other, but just create a program which generates the exact same fractal.

That kind of regularity can still be explained in the language of commonly occurring sets: For a fractal, you reserve a symbol for the overall structure, which is common (in that something like it occurs frequently), and you have a symbol to instantiate it, given a particular position, to what scale. Time is handled similarly.

Compression amounts to saying: "This is the structure of the data. Now, here's the remaining data to full in any uncertainty not resolved by its structure." The structure tells you what long symbols you can substitute with short symbols.

And no compression system can garuntee that every observed instance can be compressed to less then its original size.

True, compression only attempts to guarantee that, for the function generating the data, you save, on average, by using a certain compression scheme. If the generating function has no regularity, then you won't be able to compress, even on average.