You are correct, the format would have to be lossless for this to be maximally effective. Since MP3 was explicitly designed to encode voice-range audio efficiently, this would not be the *ideal* metric.

However, since the format is also resilient and flexible, it should have a structure - even if that complexity is hidden in the codec - with a magnitude less entropy than the mis-decrypted possible plaintexts.

But yes, you compress, than encrypt. If your encrypted data is compressible or otherwise distinguishable from random noise, than you have (exploitable, correlatable) bias in your encryption functions, or you have inefficiency/redundancy in your compression.

I would think a very limited set of magic numbers/possible hex ranges would yield the highest performance per error.