No, they shouldn't. Centralized App Stores isn't the way to go, look at recent examples of (temporarily) removed Apps like Matrix from Play Store. A decentralized App Store (e.g. based on IPFS) would be great.