I don't find the comparisons to eyelashes or false nails/polish equitable, as those items are specifically called out in GFSI codes and many regulations.
As your policy didn't previous exclude the henna, I think there's an opportunity here for you to evaluate. OP doesn't mention if it's a hand henna, or arms or face, etc. If it's on a body part normally covered by clothing or a smock, the risk is nil. If it's on an exposed body part like the hands, you can ask the employee to demonstrate whether regular washing will remove it (which I doubt it will if it's a quality product). If it can't be washed off with soap and water, you can deduce the risk of it affecting product is also nil.
But if you choose to move forward in prohibiting henna on your production floor, you'll need to call it out in your GMP's and do a company wide retraining.