Addressing people is even more complicated in Denmark. In the old days, everyone said:

Herr = Mr.
Fru = Madam = Ma'am I guess
Froeken = Miss

We also had Du = you (informal) for friends/family, and De = you (formal) for strangers/collegues/in shops etc.

Then, sometime during the 70ties, it was decided that everyone should say Du. I found it very weird to begin with, and especially when writing to someone official or sending a job application. Once you sit in front of people, it's easier. In that situation, everyone will say Du these days, and I find it natural now.

If someone in a street says Ma'am to me, I really do feel old.