The concept is sound, yes, but the execution is cut-throat. If the company is losing money on paying extra healthcare for smokers, and the chances are they pay a block amount per employee, regardless of whether they smoke or not, I mean, if
they need to test their employees, then how would the Medical Insurers know if they smoked or not?
If it
is on an individual basis, then the last option should be to drive you employee away. As I say, maybe add a clause to the contract that the company is not obliged to pay Healthcare for employees who refuse to take a smoking test, or who smoke..
Remember, these people were sacked for refusing to take a test,
not for being smokers. Some of them may have been non-smokers who simply felt the company had no right to pry.
However, by adding the option of paying your own healthcare, you leave the worker some degree of freedom of choice, rather than 'Do it or We'll sack you', which is not a form of management I'd like to see return.
Edit : It also adds the incentive to quit smoking, because the company will start paying your medical fees for you again
