Гм... А что, пакет soul разве не работает, если использовать юникод и
русский текст:

\usepackage[T2A]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[english,russian]{babel}

...

... за всю \ul{многотысячелетнюю} историю России.

?!

 Обидно...  :- (