Python Sending E-Mail with Umlauts

Question

I want to create a program in python that receives every new unread email from one of my email accounts to another email account.

So far I got everything set up. Unfortunately I have really big issues with umlauts (ä,ö,ü). For some reason I con not make it to work properly.

Here is my code:

# -*- coding: utf-8 -*-

import os, sys
import imaplib
import email
import smtplib
from email.mime.multipart import MIMEMultipart

servername = 'SERVERNAME'
username='USERNAME'
password='PASSWORD'


mail = imaplib.IMAP4_SSL(servername)
(retcode, capabilities) = mail.login(username,password)
mail.list()
mail.select('inbox')

server_smtp = smtplib.SMTP_SSL('SMTP')

n=0
(retcode, messages) = mail.search(None, '(UNSEEN)')
if retcode == 'OK':

for num in messages[0].split() :
  n=n+1
  typ, data = mail.fetch(num,'(RFC822)')
  for response_part in data:
     if isinstance(response_part, tuple):
        original = email.message_from_string(response_part[1])

        print original['From']
        typ, data = mail.store(num,'+FLAGS','\\Seen')

        body = ""
        if original.is_multipart():
            for part in original.walk():
                ctype = part.get_content_type()
                cdispo = str(part.get('Content-Disposition'))

                if ctype == 'text/plain' and 'attachment' not in cdispo:
                    body = part.get_payload(decode=True)  # decode
                    break
                else:
                    body = original.get_payload(decode=True)

        body = body.encode('UTF-8')
        body = str(body)

        print(body)
        body = "Betreff: " + str(original['Subject']) + "\n\n\n" + body.encode('UTF-8')
        SUBJECT = original['From']

        server_smtp.login(username, password)
        msg = 'Subject: {}\n\n{}'.format(SUBJECT, body.decode('UTF-8')) 
        server_smtp.sendmail(username, 'TARGET', msg)

For example: if I want to send this message: "ÄäÖöÜü&ß" I will receive this: "������������&�� ���"

Do you know what I am doing wrong? I would really appreciate your help!