Do people use them though? Both Mac and Windows have pretty much tied app sandboxing to 30% app store fees, which means the proposition is "rewrite your app to use incomplete APIs and then you can put it in our store where we'll take a big cut!"

Not very appealing. It only works on mobile because there wasn't an existing industry used to 2% fees and unrestricted APIs.

Unsurprisingly Microsoft has abandoned app store fees and mandatory sandboxing so their app store has any chance of being used. Not sure about Apple.

Can't apps use sandboxing with Apple's notary feature without needing to distro on the app store? and the incentive is the lack of a scary warning?

You can get rid of the scary warning without having to sandbox though.