With gravity and electromagnetism, the interaction strength decreases as you separate two objects. It takes only a finite amount of energy to separate two objects, actually we can even say that the amount of energy is quite small compared to the mass of the objects. A bound state therefore must exist at a lower potential energy than the constituents, else it would quickly decay.
However the strong interaction is completely different, the strength of the interaction actually increases as you separate two quarks. If you attempt to separate two quarks, you will continue to add energy to the system until you actually add enough for a new quark-antiquark pair to be created. Instead of separating the system into a pair of quarks, you will have instead created two hadrons. The condition for our original configuration of quarks to be a bound state is only that the total energy of that configuration is less than the total energy of the pair of hadrons that we would create by attempting to pull a quark out the configuration. Hence there's no contradiction with the fact that the binding energy creates mass.