First of all Marry Christmas (or Happy Hanukkah) and Happy New Year!!!
Second - I have found a solution for this problem.
Here are my steps for it:
1. Create an empty test DB (data base)
2. Download notepad++
3. Download your current DB via Sypex Dumper and force encoding to latin-1 (otherwise on utf8 or auto encoding it will be unreadable abracadabra in Russian)
4. Open DB in Notepad++ (DB is now readable with proper Russian letters) and manually change latin-1 to utf8 (it is in the first line) and save it
5. Upload your edited DB to the test DB on your server.
6. If you need to change collation_server latin1_swedish_ci (or any other) to utf8_general_ci here the simple query for SQL:
ALTER DATABASE db_name DEFAULT CHARACTER SET utf8 COLLATE utf8_general_ci;
7. Change your config.php with new DB's name and password and uncommette // $config['Mysqli']['charset'] = 'utf8';
8. If you need to zip-unzip with *.gz , please use editor like 7-Zip
That's all
Now vBulletin's search engine works perfectly without bugs