Большинство на IE сидит, надо под них затачивать.
У меня в IE 7 автогенерированное меню выглядит как BE%D1%81, а вот несколько ссылок меню прописанных руками как mysite/хобби/трава так и отображаются (в лисе все ссылки красивые)

Хочется и автогенеренные "прямыми" сделать.
Однако есть небольшое подозрение, что "кривые" ссылки поисковые системы возьмут нормально, а мои красивые рукописные проигнорируют. Возможно, я себе зря голову забиваю и единственный правильный вариант, это использование BE%D1%81.

По Вашей ссылке, в очередной раз идет обсуждение - как транслитерировать урлы.
Стоит задача оставить именно русские урлы, но без BE%D1%81

Яндекс вполне индексит такие линки. Вот и примерчик: http://yandex.ru/yandsearch?text=Работа+со+строками+в+Javascript&stpar2=%2Fh0%2Ftm0%2Fs1&stpar4=%2Fs1