The entire problem is that the users have no idea prior to installing the software, whether its legit or malware. I don't see anything in what you've proposed that solves the root problem. Yes, we can look at peripheral problems like cleanup and revoking certificates but those only affect users AFTER they've already made the choice of installing a particular piece of software.