Non dependent Prefabs (Prefabs that are not nested nor Variants) are imported in a nondeterministic order. In this case OnValidate is called while a Prefab is imported and it checks if a Prefab that is referenced by a script from the current Prefab is non null, which depending on the importing order might hold or not.

To check if a script referenced Prefab is valid we have https://docs.unity3d.com/2022.1/Documentation/ScriptReference/AssetPostprocessor.OnPostprocessAllAssets.html which gets called after all Prefabs are imported.

Following is an example of a similar validation:

ItemBlueprint.cs:
using System.Collections.Generic;
using UnityEngine;

public class ItemBlueprint : MonoBehaviour
{
public List<GameObject> referencedPrefabs = new List<GameObject>();

public void ValidateReferencedPrefabs(string caller)
{
foreach(var referencedPrefab in referencedPrefabs)
{
if(referencedPrefab == null)
{
Debug.LogError(caller + ": - Referenced prefab is null");
}
}
}

public void OnValidate()
{
ValidateReferencedPrefabs("OnValidate");
}
}

PrefabValidator.cs:
using UnityEditor;
using UnityEngine;

public class PrefabValidator : AssetPostprocessor
{
static void OnPostprocessAllAssets(string[] importedAssets, string[] deletedAssets, string[] movedAssets, string[] movedFromAssetPaths)
{
foreach(var importedAsset in importedAssets)
{
if(importedAsset.EndsWith(".prefab", System.StringComparison.OrdinalIgnoreCase))
{
var prefabRoot = AssetDatabase.LoadMainAssetAtPath(importedAsset) as GameObject;
var itemBlueprints = prefabRoot.GetComponentsInChildren<ItemBlueprint>();
foreach(var itemBlueprint in itemBlueprints)
{
itemBlueprint.ValidateReferencedPrefabs("OnPostprocessAllAssets");
}
}
}
}
}

In this case the calls to ValidateReferencedPrefabs from OnPostprocessAllAssets will log errors only for missing referenced Prefabs and the calls from OnValidate will log errors for all missing referenced Prefabs and for non missing referenced Prefabs at random.

Please note that this approach won't validate Prefabs that are already imported - they are not in string[] importedAssets. This also applies to OnValidate - if a referenced Prefab gets deleted OnValidate won't be called on the Prefab that references the deleted Prefab until it gets loaded (it's selected, imported, etc)