The default install of basic and portable MiKTeX 2.9 uses bitmap fonts for the Cyrillic charset (when the output is PDF).
This can be resolved by installing the package cm-super from the package manager (you can download the package from CTAN, mirror or another mirror).
After that, from MiKTeX Options, press the buttons "Refresh FNDB" and "Update Formats" (from both the regular and admin panels for normal installation).
The command updmap should be applied by the package manager, otherwise apply it from a command prompt.
If problems with fonts not found (for any reason) persist, run the following two commands:
initexmf --mkmaps
initexmf --update-fndb
Sources: tex.stackexchange.com, sourceforge.net, dev-eth0.de
By the way, if you need to create a local repository for MiKTeX, you need the the following four files. For MiKTeX 2.9 they are in the same folder as the packages and are called:
README.TXT
miktex-zzdb1-2.9.tar.lzma
miktex-zzdb2-2.9.tar.lzma
miktex-zzdb3-2.9.tar.lzma
You can obtain them from mirror.szerverem.hu, ftp.cc.uoc.gr, list of mirrors.