Ok, thanks. I have already tested hard-encoding the subtitles into video files but it is extremely inconvenient as it takes quite some time.
In the meantime, I have managed to get the subtitles working without reencoding. You need to copy the text-based subtitle file together with the movie file. The obvious part is that they need to have the same name (except for extension). The not-so-obvious part is that the name needs to be short. Apparently, it can only see the subtitle if the names are not too long and then the famous icon appears. Otherwise, you do not get anything.
Thanks to you all again