Esta questão está relacionada à perguntaPython IMAP pesquisa usando um assunto codificado com iso-8859-1, mas a resposta dada não está funcionando para mi

Estou fazendo a seguinte pesquisa IMAP em python:

typ, data = self.M.search("utf-8", "(SUBJECT %s)" % u"réception".encode("utf-8"))

E recebo a seguinte exceção:

...
    typ, data = self.M.search("utf-8", "(SUBJECT %s)" % u"réception".encode("utf-8"))
  File "/usr/local/python/2.7.2/lib/python2.7/imaplib.py", line 625, in search
    typ, dat = self._simple_command(name, 'CHARSET', charset, *criteria)
  File "/usr/local/python/2.7.2/lib/python2.7/imaplib.py", line 1070, in _simple_command
    return self._command_complete(name, self._command(name, *args))
  File "/usr/local/python/2.7.2/lib/python2.7/imaplib.py", line 905, in _command_complete
    raise self.error('%s command error: %s %s' % (name, typ, data))
error: SEARCH command error: BAD ['Could not parse command']

Por que é que? Como posso resolver esse problema?