I used to work on this part of CoreMedia. Opening the mp4 header is fast enough that spotlight does it in the background for every supported media file on your system.
For tens of thousands or even millions of files, inspecting the header only loads about an extra page into RAM per file. Or, since Apple already has the Spotlight index with this track data in it, 0 extra pages.
Basically, only track information that's not already in the Spotlight DB needs to be loaded so the performance should be the same as walking the filesystem for filenames.
But how fast is that? Cause Spotlight is running in the background, not blocking you from opening the file.
I think the bigger issue is just that users expect a .mp4 to open with their default .mp4 player, and in fact some people don't know about "open with" and change the extension as a way to pick the player.
Unless it's changed since I was there, Spotlight is more or less a sqlite3 database so it has about the same complexity as navigating a filesystem tree but probably with better cache affinity.
But also this concern about loading the header of millions of files is such an edge case that I don't think it matters. A human tapping on a piece of glass to play a few files would notice no difference in performance.
So if I understand correctly, if you have a file with an unknown type then change the extension to something still unknown, it'll preserve the first default editor you set for the file.
