That would be fine but it doesn't solve any of the problems really. Apple will still have control over their store. Google Play will continue to let you in and then review if they get a complaint (at least I assume that's how they do it). Ultimately I'm not sure that the business model will work. It only really applies to Android and even then most people get apps through the marketplace. Those people who want to side load apps most likely know the consequences or know someone who does and decide whether or not to take the risk.

It seems analogous to running your website code through the W3 checker. It's a certification that you did stuff right, but it doesn't stop most users from going to your site if you don't have that little badge at the bottom.