渡邉＠自己レスです。

> 例えば、'%サハンド%' で検索すると「サロンド・・・」が抽出されます。
> phpMyAdminでも、mysqlコマンドでも同様です。
> 設定ミスなのでしょうか？
>
> 環境：
> VineLinux2.6
> ※/etc/my.cnfで、"default-character-set = ujis" としています。
>
申し訳ありません。書き忘れました。
MySQL-3.23.53-0vl2を利用しています。
# 古すぎですね・・・

MLの過去ログをかたっぱしから読んでみたところ、
http://www.mysql.gr.jp/mysqlml/mysql/msg/7213

これが原因のような気がしてきました。
4.0.24あたりにしてみようと思います。

お手数をおかけしました。