User facing monitoring is a huge help here. I removed an application that hijacked the lock screen of a phone with Android 4 on it (Android only had the requirement that applications don't hijack the lock screen from the App Store for Android 5 and up IIRC). This was because of the simple monitoring that was built into Android through developer options which was simple to activate.

Far more could be done with more sophisticated user controlled monitoring tools, which could say monitor the network traffic, application accesses to any information on the device etc. No reason it cannot be done, and they may be there already.

Also device does not need to have their applications mandatorily locked to an App Store to get the benefits. Optional use of the 'official' app store is fine too, which is what isn't there on iOS. You can choose to just get your applications through the 'official' app store. Someone else not getting their applications through the 'official' app store does not magically put those applications on your device, and thus does not decrease the security you may get from the app store for you.