>A related approach might be mandatory developer registration for certain extremely sensitive permissions, like intercepting notifications/SMSes...? Or requiring an expensive "extended validation" certificate for developers who choose not to register...?

I think my overriding concern is not nuking F-Droid. I actually think that's a great solution and, interestingly, F-Droid apps already don't use significant permissions (or often use any permissions!) so that might work. Also it would be good if perhaps F-Droid itself could earn a trusted distributor status if there's a way to do that.

Or a marriage of the two, F-Droid can jump through some hoops to be a trusted distributor of apps that don't use certain critical permissions.

I think there have to be ways of creatively addressing the issue that don't involve nuking a non-evil app distribution option.