Lucene has quite poor support for Russian language.
RussianAnalyzer (part of lucene-contrib) is of very low quality.
RussianStemmer module for Snowball is even worse. It does not recognize Russian text in Unicode strings, apparently assuming that some bizarre mix of Unicode and KOI8-R must be used instead.
Do you know any better solutions?
Project http://code.google.com/p/russianmorphology/ moved to https://github.com/AKuznetsov/russianmorphology. Please take into account the new hosting of this project.
That's the beauty of open source. You have the source code, so if the current implementations don't work for you, you can always create your own or even better, extend the existing ones. A good start would be the "Lucene in Action" book.
If all else fails, use Sphinx
My answer is probably too late, but for the record, I've found analyzers from AOT project much better then those shipped with Lucene.
I used http://code.google.com/p/russianmorphology/