It's worse than that. There are a finite number of states of a message, and you can only reference that number of states of the outside system. If you think of the message as a pointer containing n bits, then you can only reference the first 2^n positions in the dictionary.

If the outside system is a probability distribution over output messages (a more general case of the dictionary you described) then the problem is synonymous with compression.