Do you need to listen for package change broadcasts to get that functionality though? Can’t you just store a list of all installed apps, then compare that local list to the current ones that PackageManager returns? That way if something is missing from your local list, you’ll know that this package was removed.
I understand the frustration though, and there are a lot of similar apps in the Play Store. Having a foreground service that registers for these events would do it, but that definitely seems like a step backwards in the battery optimization sense, and some kind of whitelist would probably make sense.