There are no mandated fees in the Bitcoin protocol so the natural response to schemes like this is for miners to simply accept fees via other means (such as the direct txout method supported by eligius since 2011, or via outputs with empty scriptpubkeys, or via out of band fees) and give users a discount for using them. The expected result would be fees migrating out of the fee area, and protocols that depend on them (like your suggestion) becoming dysfunctional. 

I previously tried to rescue this class of proposal by having the  change not be to fees but by modifying the lowness of the required hash (effective difficulty), but it's difficult to do that in the presence of subsidy.

Unrelated, as you note your proposal is no constraint if miners agree-- this is also why it fails to address the conflict of interest between miners (really mining pools), who are paid to include transactions, and everyone else-- who experiences them as an externalize except to the extent that they contribute to economic growth (not at all a necessity: e.g. many companies want to use the bitcoin blockchain without using the Bitcoin currency at all).  Still, better to solve one issue even if all can't be solved.