The relic abundance of heavy stable particles charged under a confining gauge group can be depleted by a second-stage of annihilations near the deconfinement temperature. This proceeds via the formation of quarkonia-like states, in which the heavy pair subsequently annihilates. The size of the quarkonium formation cross section was the subject of some debate. We estimate this cross section in a simple toy model. The dominant process can be viewed as a rearrangement of the heavy and light quarks, leading to a geometric cross section of hadronic size. These results can be used to construct models with ultra-heavy dark matter. They are also relevant for the cosmology of any stable colored relic.