Android Apk Installation Blocked by Play Protect

I created a Key Store for 25 years and only fill up Country Code, the Released Build + Signed APK (Both V1 and V2 Signature Versions) trigger Play Protect warning on first install. I click "Install Anyway" and the installation proceed as usual.

If I didn't click "Install Anyway" and try to install the apk again, it will show "App not installed" (it might or might now show error code -22, depending on Android version). I check the google source and found INSTALL_FAILED_VERIFICATION_FAILURE = -22. I suspect it is related to Google Play Protect.

The same happend ("App not installed") if I uninstalled the app and try to install again.

Solution 1: If I disabled Play Protect (Setting -> Google -> Security -> Google Play Protect -> Disable "Scan device for security threats"), the installation go through without problem.

I suspect this is the default Play Protect behaviour: Play Protect will popup warning upon first installtion of suspicious APK, after which it will block the installation without further warning.

Solution 2: I created a new Key Store, setting it to 50 years and fill up all the available fields. The newly signed APK doesn't get flagged as suspicious google play protect.

Solution 3: Some mentioned the Play Protect Appeals, but I didn't tried this.

2019-04-01 Updates

I tried to build an APK for testing, and Play Protect warning Play Protect doesn't recognise this app's developer. Apps from unknown developers can sometimes be unsafe. is persistent.
I generate the keystore with 50 years validity and fill up all the fields.
The app is using compileSdkVersion/targetSdkVersion 28.
As usual, play protect warning only prompt on the first attempt with Continue Anyway options. On subsequent installation attempt, the warning is no longer shown with App not installed message.
I suspect it is no longer possible to distribute non-published (Play Store) APK on device with Play Store/Play Protect without the warning and restriction.
You would need to disable Play Protect or Published at Google Play or submit to Play Protect Appeals?
There is a Google Play internal test/alpha/beta to distribute the APK, but you still need to setup the Google Play Store listing.

2019-07-01 Updates

After about 2 weeks where my new app is blocked by Play Protect, it seems to work now without any changes.

References: