What if owners of blacklisted addresses spray satoshis at every address in the blockchain and taint the whole thing? What if they do it quickly before any new rules are in place?

Most people haven't got the technical skills to move the clean bitcoins to a new address, and leave the dirty satoshis in the old address. They will just spend the dirty satoshis mixed to together with the clean ones.