I don't know if this meets all of the requirements stated, but based on a quick skimming of P2SH^2 and your Proof-of-Publication paper, here's a rough idea of an "attack" to store arbitrary data. This would require a tiny amount of brute-forcing, and it is not dust/fee-efficient, but I think it would work. I was unable to find the "2.0" discussion.
You missed the part where I said "no-brute-forcing" - I'm talking about something quite different that takes advantage of what P2SH^2 does. However, the rest of your post would work and is actually pretty clever, so sent you a tip all the same.