AND検索はうちでは普通に出来てるよ。今も実際に試した。
AND検索の場合、2つの検索語の間のスペースが半角ならＯＫ、全角スペースはダメというだけ。
よく覚えてないけど、以前からそうだったのでは（MM3の日本語ヘルプに半角スペースと書いてあった）。

検索に関しては、むしろこっちが問題。
http://mediamonkey.xn--m8jfw.jp/index.php?FAQ#p24c86cb
まあうちでは普段、基本検索や上級検索でフィールド指定で検索するから、あまり支障はない。