The aggregation−volume−bias Monte Carlo (AVBMC) algorithm is reanalyzed, and on the basis of this analysis, two extensions of the AVBMC algorithm with improved sampling efficiency for super-strongly associating fluids are presented. The new versions of the AVBMC algorithm are based on the principle of super-detailed balance and retain the simplicity, generality, and robustness of the original AVBMC algorithm. The performances of the various versions of the AVBMC algorithm are compared via applications to the simple ideal-association model of van Roij and to the superheated vapor phase of hydrogen fluoride.