How do you know they will not deny the service?
If you connect to 10 different nodes, you only need one of them to send you the branch.
Secondly, if the UTXO tree is sorted, it is possible to prove that UTXOs aren't in the tree (by giving the path to the leaf before and after where the leaf would have been inserted).
Well this seems like a subtle (but serious) flaw. What you could end up with is a small number of big nodes that have the tree, or the branches you're interested in, and you would have to rely on them to relay the parts of the tree, and they may not, and what will you do? Download all the blocks when the blocksize is huge? Once Bitcoin is big, people may notice this, but it will be too late to do anything except "protest" and hope people change things.
Another reason why bigger blocks are a problem, and this gives me more confidence in (tree-structured) subchains, which actually lets you prove the UTXO state of your wallet (or someone else's wallet you're tracking) without having to deal with DOS attacks:
https://bitcointalk.org/index.php?topic=1083345.0.
