However the failing tests seem to be embedding Python (hence test_embed) and then the initialization sequence is sufficiently different that apparently the __path__ value is either not set or it points to a non-existing directory

Good point. That's an important observation. If we cannot extrapolate the stdlib dir during runtime init then frozen modules will not have __file__ or __path__ set appropriately. That would definitely cause import of unfrozen submodules to fail. sys._stdlib_dir is where the discovered stdlib dir is recorded (and where FrozenImporter gets the value).

So, if that is the problem then:

One possible fallback for runtime-init-could-not-find-stdlib-dir is to manually walk sys.path looking for os.py (the stdlib dir marker we use elsewhere). This could be done during runtime init (or lazily in FrozenImporter, though there isn't any point in doing it lazily I suppose). I didn't do that when I added sys._stdlib_dir due to the potential cost to runtime init and because it didn't seem necessary. However, it is important if we want __path__ to work for partially frozen packages.

One thing to watch out for when walking sys.path is when the stdlib is located in a zip file (a '.zip' file on sys.path). It might make sense to use zipimporter.find_spec() (Lib/zipimport.py) for those '.zip' files. (We can't just use importlib.util.find_spec() to do the whole thing for us since FrozenImporter will find the module. It would work if we temporarily removed FrozenImporter from sys.meta_path but a hack like that makes me too nervous. We could probably get away with walking sys.path_hooks or using FileFinder.find_spec() directly, but that's overkill.)

Another possible solution is to disable the frozen encodings module if the frozen one doesn't have __path__ populated. This could be done in FrozenImporter.find_spec() for all modules it identifies as packages, returning None if (the eventual) __path__ is empty. We'd probably need to update a few other FrozenImporter methods to match.

FWIW, the matter of runtime init not finding the stdlib dir (and hence sys._stdlib_dir not being set) should probably be handled in a separate issue.