I've had similar problems recently when upgrading an existing content management system from Latin-1 to UTF-8. After extensive testing we have decided to display all website content in UTF-8 encoding, but send emails in Latin-1, because many freemail websites seem to ignore the charset directives.
If your provider happens to run an older Perl version, the Encode module might not support UTF-8 or it might not be there at all. In that case, have a look at the sub latin1 in the following example: Converting character encodings.