If a C-corp has one employee (the owner), can his Health Insurance be paid 100% by the company (and deducted by the company)?

I just picked up a client who has been doing this for years.

Of course. Why not?

Now, whether it is tax-free to the individual under Section 106 is another story.

Come again!

You need to work through the rules in the regulations under 106 (and 105) and conclude that the payment of the premiums on the employee's behalf is not taxable under those rules. Otherwise, it's taxable wages. Completely separate issue from whether it's deductible by the employer.