To achieve this, replace /usr/lib/mozilla/searchplugins/google.src with the current one from http://www.google.com/mozilla/google.src. A search for "russian" helps enjoying the before and after effect. It works here with a gtk2 mozilla; needs testing with a non-gtk2 mozilla. Should probably go into the ebuild. Another step towards "UTF-8 everywhere" :)
works for moz gtk 1.2 no worky in galeon though
Also not expected to work in galeon, because all the file does is to add some get parameters the the search url fed to google that instruct google to return the result in utf-8 encoding. Galeon only borrows the rendering engine from mozilla and does its own search thing.
Fixed in mozilla-1.2.1-r3. I also patched galeon (1.2.7-r1) to have UTF8 enabled smart bookmarks. Problem though is that it do not work for already created bookmarks (recreate or new user ...).