There's lots of regional variation in usage of 'ma'am' and 'madam(e)'. Madame in particular might evoke images of a woman that runs a brothel, actually! (see the 'Other usage' section of http://en.wikipedia.org/wiki/Madam). Sometimes 'miss' is used with women, regardless of age, in the place where 'sir' would be used for men (e.g., to teachers, in Western Canada).
A lot of women feel old when they are called 'ma'am', and feel patronized when they are called 'girl.' There is an excellent article on the American perspective on 'ma'am' in this New York Times article: http://www.nytimes.com/2010/08/29/weekinreview/29angier.html?_r=1&scp=1&sq=Ma%27am&st=cse
I was first called 'sir' by business owners, etc., at age 15 (somewhat jokingly, I'm sure). Unfortunately, there's no equivalent for women. There is always 'miss' -- however, at some point that becomes as patronizing for some women as 'girl.'
This is a repeat of the 'guy' problem, there being no female equivalent. The closest thing is 'gal'; however, 'gal' is odd or at least excessively 'flowery' in anything other than strong slang or in joking.