After looking into Unreal source code I noticed that the error does not depend on play store key at all!
It actually depends on the way UE4 looks for OBB file location(s) on the phone and it’s either bug in Install_XXX-armv7.bat file or bug in UE4 code (still present in 4.26).
My Android phone (Huawei P10) has sd-card and also had install preference “sd card” in storage settings in phone settings.
UE4 code uses Environment.getExternalStorageDirectory() API to check OBB presence and it correctly looks for OBB file on actual sd card, but Install_XXX-armv7.bat always installs OBB file into internal memory (at least in my case).
So for me the simple fix was to SET PREFERRED INSTALL LOCATION TO “INTERNAL MEMORY” IN PHONE SETTINGS. After that Environment.getExternalStorageDirectory() returns the exact same path Install_XXX-armv7.bat installs OBB to and everything works fine. That’s enough for testing, but requires some more research for shipping and publishing builds.
I suppose that in real life, player will install the game through Play and Play will install OBB into the correct location (I have yet to check this). But overal the current UE4 approach seems a bit unreliable - if player changes install preference settings between internal storage/sd card any installed UE4 game might stop working and/or will start re-downloading OBB into new location.