Knowledge of relatedness between pairs of individuals plays an important role in many research areas including evolutionary biology, quantitative genetics, and conservation. Pairwise relatedness estimation methods based on genetic data from highly variable molecular markers are now used extensively as a substitute for pedigrees. Although the sampling variance of the estimators has been intensively studied for the most common simple genetic relationships, such as unrelated, half- and full-sib, or parent-offspring, little attention has been paid to the average performance of the estimators, by which we mean the performance across all pairs of individuals in a sample. Here we apply two measures to quantify the average performance: first, misclassification rates between pairs of genetic relationships and, second, the proportion of variance explained in the pairwise relatedness estimates by the true population relatedness composition (i.e., the frequencies of different relationships in the population). Using simulated data derived from exceptionally good quality marker and pedigree data from five long-term projects of natural populations, we demonstrate that the average performance depends mainly on the population relatedness composition and maybe improved by the marker data quality only within the limits of the population relatedness composition. Our five examples of vertebrate breeding systems suggest that due to the remarkably low variance in relatedness across the Population, marker-based estimates may often have low power to address research questions of interest.