You give the correct answer in one of the options you propose: it is simply a matter of definition. It is not uncommon in physics (it is part of the culture) to include negative signs explicitly into formulas or definitions, so that the quantities themselves end up having the sign the person introducing the definition felt made the most sense or was most convenient (very often it is done so that the quantity in question will always be positive, if that is a possibility). Examples abound: it makes sense think as the drag force as negative, but a negative sign is often introduced explicitly into the formula to make the drag coefficient itself positive. Similarly for elastic constant, isothermal compressibility, etc.
The assertion you make about the biding energy having to be negative makes sense only after we have agreed on how we want to set the sign in the definition. If we agreed on the opposite definition, then the assertion would become that the binding energy must be positive. The physical content of the assertion would be exactly the same in both situations.
It is worth mentioning that the binding energy is often reported per nucleon (so, it would be the formula you present, but divided by A). Whether there can be isotopes with negative binding energy (more energy for the nucleus as a whole than for the constituent nucleons) is an interesting question. They would not be stable, of course, but could be metastable. Lithium 3, for example, is reported to have an atomic mass of 3.03078 amu (Wikipedia, Isotopes of lithium). After subtracting the 3 electrons you still have about 3.02913 amu, whereas 3 protons give you only 3.02183 amu. So, this isotope seems to have a negative binding energy, according to the formula you quote, which is also the one I am familiar with. This isotope is very unstable (very short half-life) I have seen its binding energy quoted as positive somewhere else, which I do not quite understand, but that would be a separate question.