"May contain" labeling seems like the better solution to this problem. This should be allowed for allergens that are present in the manufacturing or packing facility but not intended to be ingredients in the product.
Yes, this causes problems.
> and then if you make it a standard there needs to be testing for compliance
Why would there need to be any additional testing? If anything I'd expect "may" foods to need less testing than an accident-prone "no" food.