[Petya V4sechkin]

Windows XP HE RUS был уже установлен на ноуте при его покупке. Причем, тогда пришлось активировать Windows (звонил куда-то в Москву), а сейчас после установки с помощью RecoveryCD английской версии активации не требуется.

На RecoveryCD родная OEM SLP для Тошибы.
А вам добрые продавцы, видимо, поставили русскую версию. Причем обычную OEM (за неимением SLP), потому и активацию пришлось делать.

И, насколько я понял, на HE rus MUI не ставится?!

Официально нет.

На ноуте Acer я несколько раз переустанавливал ОС без Recovery CD (Alt+C). Есть ли аналогичная возможность переустановить OC на Тошибе 2003 г. выпуска?

Вы имеете в виду специальный раздел для восстановления? Не знаю, смотрите в документации к ноутбуку. Но даже если он есть, там эквивалент RecoveryCD (точнее, образ установленной системы).