Fonts & Character Sets ⇒ Cannot load any fontenc except for T1

[Johannes_B]

Using \listfiles to check all filepaths. I have the feeling that there are multiple TeX Live versions on your hard drive.
But to be honest, it is really hard to figure this out without sitting in front of the computer. Do you have by any chance a TeX wizard around?

[Fibonacci]

Using \listfiles to check all filepaths. I have the feeling that there are multiple TeX Live versions on your hard drive.

Actually no. Only one. Here's the relevant part of the log file with \listfiles:

*File List*
article.cls 2014/09/29 v1.4h Standard LaTeX document class
size10.clo 2014/09/29 v1.4h Standard LaTeX file (size option)
fontenc.sty
t2aenc.def 2005/09/27 v1.0i Cyrillic encoding definition file
t2acmr.fd 2001/08/11 v1.0a Computer Modern Cyrillic font definitions
***********

Just in case, I also ran mkjobtexmf, which created a fls file with the following contents:

PWD /tmp
INPUT /usr/local/texlive/2014/texmf.cnf
INPUT /usr/local/texlive/2014/texmf-dist/web2c/texmf.cnf
INPUT /usr/local/texlive/2014/texmf-var/web2c/pdftex/latex.fmt
INPUT file.tex
OUTPUT file.log
INPUT /usr/local/texlive/2014/texmf-dist/tex/latex/base/article.cls
INPUT /usr/local/texlive/2014/texmf-dist/tex/latex/base/article.cls
INPUT /usr/local/texlive/2014/texmf-dist/tex/latex/base/size10.clo
INPUT /usr/local/texlive/2014/texmf-dist/tex/latex/base/size10.clo
INPUT fontenc.sty
INPUT fontenc.sty
INPUT /usr/local/texlive/2014/texmf-dist/tex/latex/cyrillic/t2aenc.def
INPUT /usr/local/texlive/2014/texmf-dist/tex/latex/cyrillic/t2aenc.def
INPUT /usr/local/texlive/2014/texmf-dist/tex/latex/cyrillic/t2acmr.fd
INPUT /usr/local/texlive/2014/texmf-dist/tex/latex/cyrillic/t2acmr.fd
INPUT /usr/local/texlive/2014/texmf-dist/fonts/map/fontname/texfonts.map
INPUT file.aux
INPUT file.aux
OUTPUT file.aux
INPUT file.aux

But to be honest, it is really hard to figure this out without sitting in front of the computer. Do you have by any chance a TeX wizard around?

No. Would you recommend one for GNU/Linux?

[Johannes_B]

If there is a Linux wizard around willing to take a look at it, let him have a go

The solution to the behaviour described might be very simple and could be sorted out within two minutes sitting in front of the machine. But its hard to tell.

[Fibonacci]

If there is a Linux wizard around willing to take a look at it, let him have a go

The solution to the behaviour described might be very simple and could be sorted out within two minutes sitting in front of the machine. But its hard to tell.

Well, the problem is (mostly) consistently reproducible, from what I've found – even in fresh TeX Live installs in live CD environments.

As for wizards, I know of no one who knows enough about TeX. Not even in my university.