Не знаю, я себе поставил сначала UTF, то Google ищет запрос в неправильной кодировке, если аттрибуты ie и oe не указывать то запрос на русском превращается в набор вопросительных знаков.
У Оперы вообще что-то не то с кодировками под Win, особенно начиная с версии 9.5 (системы отслеживания багрепортов, увы, нет никакой, так что не знаю, как даже теперь и быть-то).
Чтобы поставить utf-8, надо вручную исправить файл настроек, он находится где-то в Documents and Settings и зовётся search.ini.
SEO Wars. Скрытая угроза.