You ask N nodes, none provides a proof. At which N you conclude that such proof must not exist?
Today I came up with an idea for pruning the utxo set that I think is simpler to implement than utreexo
I outline the idea here: https://gist.github.com/supertestnet/6aa3dbeb7cb749741c18ed9335a23a81
Discussion
I believe bitcoin asks 10 nodes for block data: 8 "regular" peers and 2 "blocks only" peers. It thus has an implicit trust assumption that at least one of them will provide data for your node to validate. I suspect the same N can be used in this protocol without any change in the trust assumptions: your only expectation is that one of your peers will provide the data (the proof) if it exists, and you then validate the proof yourself.