I would start my reply with a question for you: Is your company offer them a over time payment/extra payment when they work late/after office hours.
If the answer is no then deducting their salaries for late coming is also a strict no no. If the company cannot maintain punctuality how can you expect from employees.
Now coming to the query, Punctuality can only be imbibed with examples, the leader has to walk the talk and then the team will follow.
For example: Sumit was the Head of Purchase department in a company and used to come late every day, as he used to work till 8-9 pm every day after office hours also. The team used to work with him till 8-9 pm, but as a senior he was allowed to come late and the team was reprimanded by HR everyday for even coming 10 minutes late.
We changed the policy and asked all the people to come on time and they can leave on time, within few days things were streamlined.
Also, you can start punctuality awards for the employees, every fortnight announce a winner and give some token pf appreciation. Positive reinforcements always work. :)
Hope this resolves your query...
5th April 2011 From India, Delhi