1) Coinjoin as I see it adds some plausible deniability but the taint is still there. Anonymity is probably not the right word. If one of the input addresses is considered a red flag,
This is really a question for how _much_ these tools are used. What you're pointing to is that there is an information leak whenever the anonymity set is less than all users of the system. It's actually even worse than that: only a very small fraction of the world uses Bitcoin at all: So even if every transaction were anonymous internally to Bitcoin there would still be an information leak from the fact that you used Bitcoin at all. The same kind of thing exist for any other anonymity system: Even if Tor was perfect, you'd still be a member of the tiny set of people using Tor (or had even heard of it), and in practice there are far more leaks than that (time of day, subject matter interests, languages spoken, etc).
What this says to me is that trying to draw a hard line at "no information loss" is misguided because no system can actually achieve that when you consider all possible information sources (and, of course, real attackers are not confined to stay within the bounds of your pretty little system: they will consider all possible information sources).
In general I prefer to say these are techniques to improve your privacy. In the conventional understanding of the word privacy we realize that privacy is seldom absolute. Because of the public ledger Bitcoin's privacy is very fragile. With current use practices today snooping so simple that webpages automate it for you easily can tell you all kinds of information about who transactions with who, and how much coin they have, how much they're earning, etc. You can't always answers these questions totally cold, but as soon as someone sends you funds you have a piece of yarn to yank on, and often their privacy will more or less completely unravel.
If zero information leak is not generally obtainable then what should we consider private or anonymous? It depends a lot on the situation and the people involved. But in considering something as a tool to improve privacy I don't need to draw bright lines: More privacy is better than less (when you actually want non-privacy you can always selectively disclose to the parties you wish to disclose to).
Besides, there are not-quite-privacy related motivations here too: Bitcoin's privacy limitations are a fungibility risk: If blacklisted coins become the norm Bitcoin may become unattractive to trade with because no one wants the risk of finding out they accepted a black coin, or we could potentially lose decentralization because accepting a feed from some centralized blacklisting authority may be the only reliable way to avoid receiving a black coin. Even if coinjoin usage did nothing to make anyone "anonymous" if it made attempts at large scale coin blacklisting cause too much collateral damage and fail at birth, that would be enough justification for it.
My thinking here is if the tools are easy and cheap they can be used very widely. Above all other criteria widespread usage is what makes the difference between your "plausible denyability" and whatever you'd call actual "anonymity". I'm also more generally concerned with more casual levels of privacy: I don't want the guy at the coffee shop knowing my income or net worth. I don't want my landlord raising my rent because he see that I can afford it. I don't want my inlaws scrutinizing my purchases. Privacy is important to personal autonomy and dignity, and financial privacy can be important to protecting you from thieves and discrimination.
But because these risks are individually low probability and distant I don't want to put my funds at risk or pay a bunch of fees to achieve it. This takes "laundry" services mostly off the table as they have monitoring risk (mostly not my concern), theft risk, and fees. More abstractly, since I think other boring users would also conclude the same thing, I might expect 99% of the funds involved in such a service to be the proceeds of crimes. While recovering my privacy might be worth some risk of being falsely implicated in someone elses crime, paying for the privileged of having a 99% chance of receiving crime involved coins would be a bad deal. Anonymity systems with only one kind of user really are useful to no one, and to be useful to common boring users overheads like fees and theft risk need to be eliminated. I believe that relative to the overall scale of the economy criminal activity is small, but that only matters if you have privacy mechanisms the whole economy will participate with.
How does adding a dust address to somebody's addy change anything? This cannot be the motivation for a dust-to-old-addresses sender. There is already a tag marking every address on the blockchain: the address. I want to hear more about this "R" attack.
Assuming no coinjoin or shared wallet usage, when a transaction spends two coins paid to different addresses you can make a assumption that the a common party is probably the 'owner' of all the involved keys and the sender of the transaction. Prior to the transaction you may not have had any information that those three 'identities' (coin1 scriptPubKey, coin2 scriptPubKey, and the party paying you) were one and the same.
When someone transacts in the intended way with a fresh address for every transaction the information leak is minimized: no more interconnection happens than is strictly needed, and the interconnection doesn't snowball.
If, after you've exhausted the funds sent to a particular scriptPubKey, someone sends you a tiny amount of coin to that scriptPubKey and you spend it in a new transaction then whatever linkage they knew carries forward and your deanonymization grows as a sufficiently small payment will only be useful when spent in combination with other coins. After several applications of this its very likely that all addresses in that wallet become publicly interconnected. Turning a theoretical weakness ("You might not be very private") into an actual one.
Since those payments are necessarily small (when used to attack all users generically) and since they were non-solicited I think giving them away in coinjoin transactions is an elegant countermeasure: Its as least as good as never spending them, but it also sweeps the crud out of the UTXO set and salts the public ledger with misleading information.
