Ah, I see. How will the EXEs you create play the video, though? If they use Windows Media Player in any way, then the same error will occur. The only way I can perceive for this to work would be if the EXEs have their own video decoder built-in. Theoretically, that WOULD work, granted. It would, however, lead to licensing issues, potentially making the use of the videos illegal without obtaining rights to a video decoder.
In any case, I don't think this solution will work for me, as the problem exists on my pre-existing games. I can't retroactively edit my already-published games to embed these exe files. As for new games in development, it would be cumbersome and unprofessional to include a separate executable for every playable video...not to mention the potential anti-virus heuristics issues.
Thanks for thinking out of the box, though!
I think I'm just going to have to determine the cause instead of finding a workaround.