The risk of DoS in many of these cases could make the entire scheme unusable for as long as it's decentralized, as you can't really effectively ban the attacker. If the attacker can run 20x as many fake nodes as there are real nodes and abuse the scheme to only spend a trivial amount of computing power and bandwidth, while making the real users waste lots of it, then the system is trivially rendered unusable. Just throw a botnet at it and it's dead.

That's why I'm thinking hard on DoS prevention.

Edit: Also, regarding change addresses: You should split up your change in several parts. If everybody does that and thus generally also refers to multiple inputs for the transaction as a result, then correlation based on the BTC sums is much harder.

Edit: https://bitcointalk.org/index.php?topic=12751.msg315793#msg3157931 - So somebody else had the same basic idea over 2 years ago. Although my version (who originally was almost identical to his) now accounts for various types of possible attacks.