検索が正しくできない症状、再現できました。ME 1.5.1
サーバはXREAのs139。
PHP 4.3.11
mysql 4.0.23

mbstring.detect_orderauto
mbstring.encoding_translationOff
mbstring.func_overload0
mbstring.http_inputauto
mbstring.http_outputpass
mbstring.internal_encodingno value
mbstring.languageJapanese
mbstring.substitute_characterno value

.htaccessで
php_value mbstring.internal_encoding UTF-8
php_value mbstring.http_output UTF-8
php_flag mbstring.encoding_translation On
などを試みるも症状は変わらず。
根が深そうですなこれ。