Here's is the answer from the horde developers regarding the issue:
"From RFC 6855:
Once an IMAP client has enabled UTF-8 support with the "ENABLE
UTF8=ACCEPT" command, it MUST NOT issue a "SEARCH" command that
contains a charset specification. If an IMAP server receives such a
"SEARCH" command in that situation, it SHOULD reject the command with
a "BAD" response (due to the conflicting charset labels).
Bottom line: your IMAP server is broken.
Oh, and since we're using SORT and not SEARCH, from the RFC's errata:
This also
applies to any IMAP command or extension that includes a charset
label and associated strings in the command arguments. Such
extensions presently include SORT, THREAD and MULTISEARCH. "
