Все верно.
Поиск не реализован на стороне IMAP сервера mail.ru. Он просто не принимает команду поиска и отвечает "не знаю, чо от мене хочете".
Пользуйтесь поиском из главного меню, ищет сразу во всех учетных записях, и не на сервере, а в уже загруженных сообщениях.
PS - в mail.ru ввели IMAP в конце лета 2012, про поиск еще осенью ответили "знаем, скоро будем делать".