Actually, no, the local part cannot be in anything other than ascii (see RFC 5335, which desires to address this problem among others).  Also, an encoded word cannot occur inside quotation marks.  If you correct those two bugs, you can generate an RFC-valid address using Header.append.

There is a project underway to make all of this header parsing and formatting stuff work better: see the http://pypi.python.org/pypi/email.

By the way, this is easier already in python 3.2.  There you can do:

   >>> formataddr(('Nameß', 'weofij@fjeio'))
   '=?utf-8?b?TmFtZcOf?= <weofij@fjeio>'