No compression algorithm can compress all input messages?
What you are missing is that you need to consider all bits of size 3 or less. That is: if in a compression scheme for bits of size 3 or less we compress one of the 3-bit strings to a 2-bit string, then some string of size 3 or less will have to expand to 3 bits or more.

A losless compression scheme is a function $C$ from finite bit strings to finite bit strings which is injective, i.e., if $C(x) = C(y)$ then $x = y$, i.e., $C(x)$ uniquely determines $x$.

Consider an arbitrary compression scheme $C$ and let $S$ be a set of binary strings. We can express how well $C$ works on $S$ by computing the ratio
$$\text{CompressionRatio}(C,S) = \frac{\sum_{x \in S} \mathrm{length}(C(x))}{\sum_{x \in S} \mathrm{length}(x)}.$$
A small compression ratio is good. For example, if it is $1/2$ that means we can on average compress strings in $S$ by 50% using $C$.

If we try to compress all strings of length at most $n$ then we are in trouble:


  Theorem: Let $S$ be the set of all strings of length at most $n$ and $C$ any compression scheme. Then $\text{CompressionRatio}(C,S) \geq 1$.


So, the best compression scheme in the world is the identity function! Well, only if we want to compress random strings of bits. The bit strings which occur in practice are far from random and exhibit a lot of regularity. This is why it makes sense to compress data despite the above theorem.