It's a problem if you need a fucking banking app for example, and the bank won't let you sideload it and you're running a deGoogled OS. Then you suddenly need a backup phone with the full surveillance Android just to do banking.
But is there anything stopping them from implementing that?
Afaik this is just a Google play API and the app checks using the API if the current user is licenced or not. Why couldn't just any other store just do the same thing?
They can. IIRC, Amazon apps would check to make sure the Amazon App Store was still installed. And I'm pretty sure Netflix games stop working when you unsubscribe from Netflix