Could miners commit to the set of UTXOs being expired in each block, instead of requiring an SPV proof from spenders?
I believe this would remove the burden on wallets to construct proofs, and allow pruned nodes to validate spends simply by tracking which UTXOs were previously expired. It also opens the door to decoupling pruning from spending fee penalties: dust UTXOs could be pruned AND subject to a higher spending fee as a deterrent, while older UTXOs that are simply considered unlikely to be spent (such as suspected lost coins) could be pruned without any spending penalty.