It all depends on the country of origin of the person you are dealing with. In Brazil, for example, is very common to both handshake and give a cheek kiss on women after the first meeting, even if in a formal environment.
Agreed, I'm American but went to a French business school. I am still completely thrown off even with cheek-kissing women, and god help me when one of the guys goes in for the double-double.