Pour envoyer un mail en non-ascii (charset au choix, latin1 ou utf-8 par exemple), il faut faire:

import mimetools, smtplib
from email import Header
from cStringIO import StringIO

encoding = "quoted-printable"
mfile = StringIO(body)
newmfile = StringIO()
mimetools.encode(mfile, newmfile, encoding)
body = newmfile.getvalue()
body = ''.join([ c for c in body if ord(c) != 0 ])

msg = """Content-Transfer-Encoding: %s\r
Content-Type: text/plain; charset=%s\r
To: %s\r
From: %s\r
Subject: %s\r
\r
""" % (encoding, charset, to, mailfrom, str(Header.Header(subject, charset)))
msg += body

s = smtplib.SMTP(smtphost)
s.sendmail(mailfrom, to.split(","), msg)
s.close()