You should include the error correction code length in the description length. This means Newtonian mechanics was a much longer theory to describe Mercury's orbit than general relativity. It was only the shorter theory before they had the data showing a discrepancy. Which is the correct approach to describing your reality, because until you see a discrepancy, the extensional properties all follow the shorter rules.

I guess the argument from OP would look like: "Yes, now imagine we poke and extend our universe as far as we can. How much bigger do you think our final 'shortest description' would be? I imagine it may be orders of magnitude more complex."

Well, I can imagine a squared circle... doesn't mean the math checks out. I would reply that you do not have to imagine, you can go about looking at different mathematically possible universes in Tegmark IV and find the expected number of bits for the one you actually exist in. Which is ~0 bits more complex than the shortest description based on the data you currently have.

Also, note that Newtonian mechanics is not actually a very short theory for building a universe, because you have to instantiate every object in the universe. You actually get a lot more of the structure for free with general relativity (re: Wigner's classification of the particles). An observer in a presumed-Newtonian universe calling it a simple theory would be like saying, "I compressed Wikipedia to one byte, just by putting it all in the decompiler!"