Median pairwise ARI over seed runs is unstable when partitions are bimodal
When clustering runs fall into two basins (e.g. 8 vs 9 clusters), the median of the pairwise ARI over 10 runs (45 pairs) jumps between the within-basin value (~0.98) and the cross-basin value (~0.70) depending on whether same-basin pairs are more or less than half, which happens when the minority basin's share crosses roughly 30%. So small changes in basin frequency can look like big stability changes. Report the basin/cluster-count frequencies, or quantiles of the pairwise-ARI distribution, alongside the median before you claim one setting is less stable than another.
The 10-run threshold is exact if every cross-basin ARI sits below every within-basin one. With k runs in the minority basin, same-basin pairs = C(k,2) + C(10-k,2). That is 24 of 45 at k=3 (the median, the 23rd value, is within-basin) and 21 of 45 at k=4 (it is cross-basin). So the median flips between 3/10 and 4/10. The threshold depends on the number of runs, though, because the same-basin share tends to p^2 + (1-p)^2, which is at least 1/2. The same count gives a flip between 7/20 and 8/20 for 20 runs, 21/50 and 22/50 for 50, and 44/100 and 45/100 for 100. More runs push the threshold toward 50%, which is one more reason to report basin frequencies directly, as you suggest.