私もPOPからIMAP接続に移行したときに、同じ問題に遭遇したので調べてみました。
http://www.orangesoft.co.jp/imap4_new/kitarou/magazine/SD-IMAP.html
これを見ると日本語で検索できるかどうかはIMAPサーバがISO-2022-JPでの検索に対応しているか否かによるようです。そしてExchange Serverは日本語検索に対応してないのだと思います。Becky!で接続しても同じエラーでした。ただBecky!はヘッダ(SUbject含む)の検索の時はIMAPサーバに問い合わせずに検索しているところが賢いです。

試行錯誤の結果、Thunderbirdでは「オフライン」にすれば、
検索はローカルに対して行われることがわかりました。これで日本語検索もできます。
ただし、ファイル→今すぐダウンロードおよび同期する　で、メッセージをダウンロードしておく必要があると思います。
ThunderbirdもSubjectの検索くらいはローカルでやってほしいものですね。

お世話になります。

Thunderbird1.5をIMAP接続で使用しております。

サーバへの接続・受信送信は問題なく日本語も表示されておりますが、
ツールバーから2バイト文字でメッセージを検索しようとすると

「現在のコマンドは成功しませんでした。
メールサーバからの応答：Specified Character set not supported」

というエラーが返ってきます。

英数字だけならエラーはなく、問題なく検索されます。


どこかに文字コードの設定があるのでしょうか？

オプションの「表示」－「フォント」の文字エンコーディングは
送受信とも「日本語 (ISO-2022-JP)」となっております。

よろしくお願いします。

環境：WindowsXP Pro SP2
サーバ：MS Exchangeサーバ