I've tried:

use locale;
use POSIX qw (locale_h);
....
setlocale(LC_CTYPE, 'Russian_Russia.20866') or die "Can't set locale: 
+$!";
        foreach $name (sort keys %authors) {
                ($letter) = ($name =~ /^(.)/);
                $letter = uc $letter;
                if ($letter ne $last_letter)
                {
                      print IND "<h2>$letter</h2>\n";
                        $last_letter = $letter;
                }
                print IND qq{<a href="$authors{$name}[1]\\index.html">
+$authors{$name}[0]</a><br>\n};
        }
[download]

Strange enought 'uc' works and 'sort' does some mysterious randomizing instead of it's purpose. Maybe this the locale mechanism in Win2k is broken, or the problem is that my current locale is not russian?