What about a sandbox where all programs that came from the internet were locked in except for verified binaries. Then make it difficult to add new certificates, like require the user to enter a password (perhaps different from their login). Have microsoft say no program should require this, and as long they do a decent job of adding certificates themselves most users will not even bother learning how to.

For those users, I guess we'd hope they don't install their own certificates and Microsoft/Apple/Google/Canonical can invalidate the Bonzi Buddy certificates for bad behavior.

You're right that it's a difficult problem and probably unsolvable but IMO that doesn't mean we can't reduce it to much less than it is currently.