When external storage is not available and it's not about storage space, rebooting real device fixes this error.
My log shows these lines :
PackageManager: Package ... could not be assigned a valid uid
PackageManager: package setting is null
PackageManager: Skipping remove dir for ...(user:0, appId:null)
PackageManager: Package couldn't be installed in /data/app/...
PackageManager: com.android.server.pm.PackageManagerException: Creating application package ... failed
PackageManager:        at com.android.server.pm.PackageManagerService.scanPackageDirtyLI(PackageManagerService.java:10630)
Main cause seems the exception in PackageManagerService :
    pkgSetting = mSettings.getPackageLPw(...);
    if (pkgSetting == null) {
        throw new PackageManagerException(INSTALL_FAILED_INSUFFICIENT_STORAGE,
                "Creating application package " + pkg.packageName + " failed");
    }
For a not-installed user application without shared user, used code in Settings is :
private PackageSetting getPackageLPw(...) {
    // Assign new user id
    p.appId = newUserIdLPw(p);
    if (p.appId < 0) {
        PackageManagerService.reportSettingsProblem(Log.WARN,
                "Package " + name + " could not be assigned a valid uid");
        return null;
    }
}
// Returns -1 if we could not find an available UserId to assign
private int newUserIdLPw(Object obj) {
    // None left?
    if (N > (Process.LAST_APPLICATION_UID-Process.FIRST_APPLICATION_UID)) {
        return -1;
    }
}
private void removeUserIdLPw(int uid) {
    if (uid >= Process.FIRST_APPLICATION_UID) {
        final int N = mUserIds.size();
        final int index = uid - Process.FIRST_APPLICATION_UID;
        if (index < N) mUserIds.set(index, null);
    } ...
}
So there is some problem with removeUserIdLPw logic or uninstall not calling it to free app user id, which needs some detailed uninstall logs I don't have at the moment.