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 set, which was only visible via xattr.

$ xattr /path/to/file.mkv

After removing the special quarantine attribute with, the prompt was gone and did not re-appear so far.

sudo xattr -r -d /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.