Does anyone believe that over the years these companies will change their behavior? Because what I see is that the list of companies will get bigger and bigger. There will be more control, less privacy, more KYC/AML and more blacklist of supposedly tainted coins.
"Taint" becomes real if enough people believe it's real. So this will depend on the users, but given that many users accept KYC-demands, they'll probably go for this too. I don't have high hopes.
Privacy changes no the protocol level could help, but I have no idea how likely that is to be implemented.
I'm not sure they would help a lot to be completely honest. Any service committing to this whole 'taint' thing would for one, heavily resist such a change to Bitcoin and maybe even try to fork it or some shenanigans like that (of course, not before spreading enormous FUD about the proposal and telling everyone that it's initiated by criminals, to protect other criminals). And secondly, if something like this were to be implemented, it would probably be optional (if not just for backwards compatibility) and they'd just define any transaction that uses this new feature 'tainted'.
In the end, even if implementing privacy on protocol level would solve all our issues and exchanges & authorities would suddenly accept that they can't easily track Bitcoin anymore (highly unlikely in my opinion), I'd like to bring up one question. Do the people who currently use Bitcoin with 0 privacy (who would gain some by this procedure), deserve it? Do people who are ready to sell out their own PII without blinking twice, who are ready to run with all the 'criminal tainted UTXO' nonsense, deserve protocol-level protections of their privacy?