I knew there was a bug I'd forgotten about!!!
I don't know for sure if this is related or not, but I recently re-jigged a couple of drives and drive letters. All of my library was fine, except for my videos. The dir structure was the same, but the drive letter was new.
Quite rightly, MC displayed all my videos with red "unavailable" crosses. Now, (here's the bug bit) with MC in either "all media" or "video only" mode, doing a library update with "remove missing files" ticked did not remove the broken files from the database. In the end I just did a search and replace to fix the database, but still, they should have been cleaned from the database, shouldn't they?
The only thing I can see that might affect this is that they were originally on drive J:\ and that drive letter no longer existed. Did MC just assume that J:\ must be a removable drive?
-marko.