I think anything is fair game that was reasonably doable back in 1983.
Cartridges have been used from the beginning, at first they were just 16 kB. Games have been released in cartridge format from 8 to 512 kB.
It's really impressive to be able to include any type of decompression when total budget per sample is just 21 clock cycles on a system where one instruction takes 2 to 8 clocks.
So I think you're underrating the achievement here.