Прошу прощения за повторный пост, но никак не могу разобраться. Проблема описана вот тут:
http://www.linux.org.ru/profile/gene/view-message.jsp?msgid=1594274
Самое забавное, что если переключать раскладку не через Mule, по С-\, а в xorg, в Гноме -- то все работает...
Вещей, связанных с какой-то настройкой i-search в связи с UTF-8 и кириллицей -- я не нашел.
Если у кого-то работает поиск в emacs с UTF-8 и русским -- поделитесь, пожалуйста, .emacs.