In modern use in American English, the term ma'am has gained quite a bit more use than madam:
In modern use in British English, madam is slightly more popular than ma'am:
As a native American English speaker, madam seems a bit archaic but does not necessarily connote a tie with a brothel unless you refer to someone as a madam. For example, the Oxford English dictionary provides the following example for madam of a brothel:
1959 N. Mailer Advts. for Myself (1961) 279 A rather remarkable woman who had been the madam of a whorehouse.
But as a form of address, it is used differently:
1956 N. Algren Walk on Wild Side ii. 122 It's not a pot, Madam. And it's strictly not for sale.
The typical terms I've heard are miss for younger females and ma'am for older ones. You could potentially refer to someone as madam or ma'am in either spoken or written communication. In formal writing, for example to someone whose name you do not know, use madam in both cases. For example:
When addressing a letter to the holder of a particular position without knowing the name or gender of the addressee, it is common to write “Dear Sir or Madam,” (or in the United States, “Dear Sir or Madam:”
This holds in both American and British English.
In less formal writing or speech, I would suggest using whichever term is more popular for the community you are in--ma'am in American English, and madam in British English. In both, madam will seem a bit more formal.