Figured it out, it did have to do with the sampling strategy.
Since BatchNorm requires mini-batches as a proxy to the population statistics the triplet samples should be selected randomly across many classes, instead of single-class batches.