After some research I found that all the files had the special permission
com.apple.quarantine set, which was only visible via
[email protected]:/Volumes/Media:$ xattr /path/to/file.mkv com.apple.quarantine [email protected]:/Volumes/Media:$
After removing the special quarantine attribute with, the prompt was gone and did not re-appear so far.
[email protected]:/Volumes/Media:$ 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.