The heterogeneous nature of HLA information in real-life stem cell donor registries may hamper unrelated donor searches. It is even possible that fully HLA-matched donors with incomplete HLA information are not identified. In our simulation study, we estimated the probability of these unnecessarily failed donor searches. For that purpose, we carried out donor searches in several virtual donor registries. The registries differed by size, composition with respect to HLA typing levels, and genetic diversity. When up to three virtual HLA typing requests were allowed within donor searches, the share of unnecessarily failed donor searches ranged from 1.19% to 4.13%, thus indicating that non-identification of completely HLA-matched stem cell donors is a problem of practical relevance. The following donor registry characteristics were positively correlated with the share of unnecessarily failed donor searches: large registry size, high genetic diversity, and, most strongly correlated, large fraction of registered donors with incomplete HLA typing. Increasing the number of virtual HLA typing requests within donor searches up to ten had a smaller effect. It follows that the problem of donor non-identification can be substantially reduced by complete high-resolution HLA typing of potential donors.