Another approach is to have "blocked variants" instead of "reserved variants". A "reserved" variant belongs to exactly one package, so you can activate it without checking for conflicts. But a "blocked" variant would not be reserved for just one package, it could be a blocked variant of multiple packages. Therefore, before you can activate a blocked variant of a package, you need to check whether it is also a blocked variant of any other packages (and check for any other restrictions on its activation). When packages are presented to registrants, the blocked variants would not be shown, because they don't belong to the registrant. The registrant will not know whether a variant can be activated until they try (because inactive variants are not reserved for just one package).
I just thought of a related problem. Suppose W and X are variants, and X and Y are variants, and Y and Z are variants, but no other pairs are variants. Suppose someone registers W, which reserves X, and someone else registers Z, which reserves Y. The two registrants can then activate their reserved labels, and now X and Y (which are variants) are registered to different people.