As you both suspected the files were not fresh but had been deleted from the library and then re-imported. This was never a problem (for me anyway) in MC18 so it would appear that the behaviour has changed somewhat in MC19.
It is definitely long-standing behavior, since at least MC16 (but probably prior). It tracks deleted files for a few reasons:
1. This enables the "don't reimport files I removed" feature of Auto-Import.
2. It can save your butt if you accidentally remove a file (which, otherwise, would cause you to lose any metadata not saved to in-file tags, and require a Library restore to correct).
3. When you do re-import a previously deleted file, it is much faster because it essentially just marks it "undeleted" and moves it from the deleted items database back to the active one. It doesn't require any of the "analysis" routines to be run, which can be "expensive" (since they have to decode the files).
One thing that I have found rather odd though is that if I delete a file in the library that has got the correct 'Media Sub Type' of 'Other' and then just re-import it again I can see it come back into the library with the correct 'Media Sub Type' of 'Other' as before but then I can watch it change the 'Media Sub Type' to 'Movie' a couple of seconds later. Why would this be the case when it had never had a Media Sub Type of 'Movie' before this.
I don't think this is right and maybe something is a little broken in there. It sounds to me like the automatic Media Sub Type analysis is being re-run on reimported files, even though the rest of the automatic metadata "massaging" (Carnac and Tag On Import) are not.
The only thing I'm not sure of is if you also made sure there wasn't a JRSidecar file on disk with the "bad" (Movie) information in it. MC does use those (Sidecar files always win, like embedded tags) when re-importing a previously deleted file, the assumption being that some other copy of MC (or another Library) could have "touched" the files in the interim. Basically, embedded tags always win, and JRSidecar.xml files are embedded tags for video file types that don't otherwise support embedded tags.
So, one addition to syndromeofadown's instructions above is to ensure you also delete from disk any JRSidecar files that belong to the test file. You have to be clever, though because Auto-Import is too quick if you try to do it with that turned on (the order you do things in counts, to a great degree). If I'm ever testing Tag On Import rules, this is the process I follow:
1. Disable Auto-Import.
2. Right-click > Library Tools > Remove Tags
3. Remove the file from MC, and from the Deleted Items database.
4. Delete the JRSidecar file.
5. Re-import by going to Tools > Import > Run Auto-Import Now.