I don't mean dust outputs (in the sense of outputs locking a smaller amount than the dust limit), but outputs which cannot be spent because they do not correspond to any private key but are simply fake data, such as the stuff which is stuffed into Stampchain/OLGA transactions.

There seem to be cryptographic methods to distinguish them (or at least some of them) from those that can be spent, if I understood previous discussions with @gmaxwell about that subject correctly. If that is not true and I understood it wrong, nodes could simply run the tools proposed in this "BIP" ("ord", the Stampchain tools etc.) each one independently, without any consensus changes, and delete the UTXOs these mark as data transactions. Nodes could even share snapshots of "invalid UTXOs" to avoid having higher costs due to running tools like "ord" all the time, but without imposing anything of that to other nodes.

In any case, it doesn't make sense at all to "invalidate" those already-unspendable UTXOs by consensus like this "BIP" proposed, and I fully agree with you that the UTXO set should never be "touched" by consensus methods. The nodes themselves should select what they're considering worthwile to preserve and what not. As I wrote already, if the proceed too agressively, they will later have higher syncing costs - just as Knots nodes have which reject OP_RETURN transactions over 83 bytes and later have to accept them anyway when they get included in blocks.

Anyway the definitive solution would be a widespread adoption of Utreexo (where the UTXO set isn't stored entirely, but instead a hash of it).