Reason: Mail should be set to always use Unicode as the default encoding for new emails. This can of course be done manually from the Message » Encoding menu when typing an email and before sending it, but it's a pain to do it manually, and there's no menu option nor preference to set this as default
Solution: Open Terminal and login as root. Then execute the following command to set Unicode as the default encoding:
defaults write com.apple.mail NSPreferredMailCharset "UTF-8"
Restart Mail and try again.
[robg adds: I tested this one, and it doesn't seem to work for me. However, I can't correspond with the Anonymous author, so I'm running it to see if it works for anyone else. Even with this value set, creating a new message and checking the encoding showed it set to "automatic." Can anyone get this to work?]

