Polymorphic contracts are the superior upgrade model. If you have thousands of token balances and allowances it’s much cheaper to upgrade the code in-place than to migrate to a new contract. If it’s too much work for the evm to ensure all of the storage slots are cleared, just don’t do it; it would save me the trouble of resetting all contract state. Most self-destructs are for contracts without state; very few contracts self-destruct with remaining state.
Instead you could incentivize other contracts to clear it out of the trie manually. A new opcode could point out external storage corresponding to an account without code and clear it for a gas refund.