cyrillic and sort order (ORDER BY)

Hello,

My problem is that ORDER BY does not alphabetically order strings in
proper way. Worst - it does sometimes work right but I can't find out
exactly why. But after a while it stops until I rebuild and
reconfigure.

I have read *everything* I managed to find in the archives and the
docs. I am using RedHat 6.2, 2.2.14; PostgreSQL 7.0.2 (at the start),
now (hoping it would have magically save me from this nightmare)
7.0.3. Built with --enable-locale and --enable-multibyte=WIN (does
this mean more than the default encoding choice for createdb?; I have
used KOI8 with the same "success"). I have LC_ALL set to ru_RU.KOI8
and a database with encoding KOI8. The postmaster is started with
these locale settings. I use charset.conf with the shipped recoding
tables. All my clients are win. I hope I haven't missed something
important. Can someone, please, help me with a little. I have spent
huge amounts of time on this and all get is an erratic behaviour
which drives me crazy. I would have preferred if it was not working
at all.

Thank you for your time.