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 on the protocol level could help, but I have no idea how likely that is to be implemented.
It's possibly too late for that. Given the size of the market, and how many do not want to deal with Monero, or view such transactions with more suspicion, at this point I really wouldn't be surprised if major exchanges and businesses decided to stay on the old chain without privacy, assuming they wouldn't have been able to successfully torpedo efforts to improve BTC at all.
I'm not that sure about this. Look at Lightning: it's in a way 'protocol-level privacy' (just one layer higher), and some exchanges added or plan to add Lightning support for deposits and withdrawals.
And since improved privacy was always one of Lightning's selling points, I'm not sure how customers would react if suddenly certain LN payments were declined / stolen. Hopefully more outrage than when this happens on-chain, where unfortunately as we determined, lots of people bought into 'well, the blockchain is transparent (no privacy, just pseudonymity) and I guess I got bad coins'.