Disclaimer: I have not looked into the details of how P2SH^2 or even P2SH works yet.
I also think it's not possible to prevent embedding data. In baddw's scheme, pre-generating dozens of vanity-like addresses for the "alphabet" addresses should be an easy one time brute-force if we limit the number of bits per address.
Yeah, you're basically limited by how much space you have for that dictionary. For instance a 32-bit brute force dictionary, stored as 32-bit seeds, would be 17GiB.
Could you not then embed the data by linking your alphabet addresses to all the vins/vouts of your transactions? Most of it could just be sending coins back and forth between your own "alphabit" addresses.
For the non-brute force solution, embed your bits into all the transaction values. ABCD can just be values in vout[1]vout[2]...etc...to your own addresses.
You guys are still all missing a even deeper implication of P2SH^2. I'll give you another hint: Does data need to be stored forever to prove it was published once?