No good, easy to sybil attack. If someone wants it badly enough, they can spin up enough nodes to be 70% of the network.

Mining is already a consensus mechanism, what you want is to change the consensus rules that everyone follows. There were a few ideas mentioned on the mailing list on this topic, but ultimately what it comes down to is trading the flexibility of script for rigidity in ensuring that all UTXOs can be spent. Essentially, the mechanism for doing this would be to require that every output also carry a proof that the output is spendable, i.e. a signature. However, this severely limits what script can do, to the point that script wouldn't really exist. I think there would be a lot of additional logistical nightmares as well (e.g. senders and receivers now need to coordinate in order for the sender to make a transaction).

Furthermore, this wouldn't even stop data storage in Bitcoin. Sure it would make it harder, but steganography is an entire field dedicated to hiding data in things that are not meant to store such data. It would still be fairly easy to shove data in bits and pieces into pubkeys and hashes, it just takes a little bit of work to grind a couple bytes of a hash or pubkey to be the data that you want to embed. And since this is extra inefficient, the instances of this data would result in massive/lots of transactions.

Lastly, just because a UTXO is spendable by someone doesn't necessarily mean that it will be spent. So even with such a scheme, we could have tons of UTXOs that encode some data inefficiently, and someone is able to spend them, but ... maybe they just don't, and they still have polluted the UTXO set.