[Sham]

кодировка htaccess должна соответствовать кодировке кириллицы из заголовка запроса (имхо только в юникоде utf8). Отследите запрос в разных браузерах, как там кириллица передается. Если urlencoded, то имхо в регекспе надо учитывать и такой вариант. Тем более, в браузерах есть настройка "кодировать урл".
Файл htaccess дб в кодировке utf8 (кодировка URL) или в регекспах учесть urlencoded символы ("символ" - %F1%E8%EC%E2%EE%EB), т.е. добавить знак процента "%" в скобки.
Если сайт не в кодировке UTF, то браузеры имхо по любому кодируют неюникод-символы в урлах.