The iOS App Store does the same thing with changing the rules in the middle of the game, but it is not subject to potential irrelevance because it is the only place to get software for iOS devices. So the obvious solution for Apple is to make the Mac App Store the only place to get software for MacOS. I'm actually a little surprised this didn't happen in 10.8.
By default Mountain Lion can only run software from the App Store or by developers Apple has specifically certified. You can tune this restriction both up ("App Store only") and down ("any software can run").
There is no "special certification", it's just a matter of creating a developer account and generating a certificate.
Also, right-click -> open will bypass the verification under the assumption that if you know about that command, you probably somewhat know what you're doing.