It did it every time and for every file, which was very annoying — to say the least!
After some research I found that all the files had the special permission
com.apple.quarantine set, which was only visible via
$ xattr /path/to/file.mkv com.apple.quarantine
After removing the special quarantine attribute with, the prompt was gone and did not re-appear so far.
sudo xattr -r -d com.apple.quarantine /path/to/file.mkv
I can only speculate that the increased security measures in High Sierra automatically flagged certain files. Why it only affected MKV and MP4 files on my system, I do not know. I think the false-positives were caused by a faulty heuristic, or something similar. But your guess is as good as mine.