If the videos are saved in the memory card, try to remove the memory card then insert it back to the device. Have you tried connecting the phone to your PC and use either Mass Storage or Nokia Suite to check if the video files are there and delete them? If not, try doing so.
You may perform a soft reset. Go to Menu > Settings and Phone > Phone management > Factory settings > Restore. This will restore all the customizable settings back to its factory default. Why they are still on the list could be a software glitch so you may also try to re-install the software of the device to possibly solve the issue. I don't think there's a separate update for the video gallery. Normally, this is included in general software updates for the said device.
Once a video is taken using the phone's camera, the phone will use the DCIM folder. If the video is coming from a different device or from a PC, you can save it under the Videos folder of either Mass memory or memory card.
It could be possible to use one folder for all the videos but it may be a tedious job. Since it is not recommended to copy the videos taken from a different device or from a PC to the DCIM folder, you will have to do the other way and that is to transfer the videos from the DCIM folder to the Videos folder every time you will use the phone to capture a video. I haven't tried it but it should be possible. 
