If eligible employees are paid additional compensation for not participating in a high-deductible employer health program in lieu of an employer contribution to an HSA, must the additional comp be paid through a 125 plan to avoid taxation on the amount to all employees?

How would you be able to run that additional compensation through the 125 plan? It seems to me that would be taxable compensation to anyone who received it. Of course, the employees could elect to use that money in either the medical FSA or the dependent daycare FSA, and then it would not be taxable.

It appears that employees have a choice between medical benefits under the HDHP and cash. That is what section 125 is all about. If you don't offer the arrangement under a section 125 plan, all persons who elect the HDHP will have taxable income to the extent of the amount available if they had not chosen the HDHP coverage, even though they don't get any cash. Of course, all persons who choose no HDHP will be taxed on the cash they receive.