Rule number one:
The more content specific encoding the better.
You wouldn't get good results if you just compressed a jpeg or an mp3 file as is.
But if you unpack the compressed data and recompress it with a better algorithm, you should be able to get much better results.
You can even skip irrelevant things in the file completly. For example, the mp3 frame header is largely useless except for the cases where the values change (not likely). Similarly,
error correction data in disc images and shared decompression tables can be eliminated.
You can also do things like throwing away data that will never be used, such as big metadata chunks (the same album picture embedded in every mp3 file?) and palette entries in pictures that are never used.
But overall, the compression table is important for the size, pick a too small one and things wont work out. Pick a too big one and you might be carrying unused data.