Yes, but this applies to every certification, including the thousands of certifications we have today for all sorts of products. Generally the quality of the label will depend on the consumer demand for it. The more it's worth the more money the certification authority will have for auditing and detective work and the more miners who secretly violate it would have to lose.
None. The protocol would be unaffected.
You would need:
1. Someone to start a certification authority, do the auditing and write the software necessary for handling the payouts.
2. An extension to the Bitcoin client that allows miners to treat outputs to certain addresses as if they were fees.
3. An option in the Bitcoin client GUI that allows users to specify an output address for an "addressed fee" instead of a standard "open fee".
(4. Transactions with an "addressed fee" would get relayed with the same low priority as transactions with no fee.. Perhaps users who have the same addressed fee set in their options could relay them with priority. Definitely some thought is needed on this issue, but I don't think it's insurmountable by any means.)
If Bitcoin transaction fees were a million dollar business, I would be the first to help start a certification authority for carbon neutral miners. As of right now, Bitcoin is tiny and obscure and we have much more basic and immediate problems to solve than how to fairly allocate 15$/month in fees.
Well, the reason I said that was because certification authorities would be kind of centralized whereas Bitcoin is all about decentralization. However thinking about it more, there would be nothing to stop new authorities entering the market to compete with existing ones, so perhaps this not much of a problem after all.