If the videos are on your memory card it may be an indexing issue...
Unmount the card in Storage Sense and then reboot the phone. Open your preferred video player and let it search for media.
Another user reports fixing the issue by connecting the phone to Visual Studio Developer tools, but that may be coincidental as I know connecting to Windows Phone App for Desktop also fixes indexing errors I've had. It is simply getting the card indexed however possible. Either on the phone or via PC interaction.