Email body encoding problem with Cyrillic letters

Question

All emails sent from a website are received as unreadable characters in body.
The email title is displayed properly though.

The site is only in Russian language. This happens on a clean install as well.

Here are the headers just in case:

MIME-Version: 1.0
Content-Type: text/plain;
  charset="utf-8"
Content-Transfer-Encoding: quoted-printable
X-Mailer: Drupal Webform (PHP/5.2.17)

This happens no matter the email provider (Gmail, Yahoo etc.).

Which settings should be changed so the emails are sent properly?

Thanks