Thanks for the update, fastnfurious. Removing the battery is actually the same as to a simple reboot. Just to verify, do you mean the video that you successfully recorded still won't show up in the gallery even after rebooting the phone? Do you have a memory card inserted in your Asha 300? If yes, try to go to Menu > Applications > Files, and see if the videos that you recorded will show up under the Videos folder. Try also to connect the phone to a PC via USB cable to view the recorded videos using Nokia Suite or Windows Explorer.
By the way, when did this issue start to happen? Did you change any phone settings or downloaded any particular app prior to this issue? Make sure that the phone's software is updated. Check this link: Nokia Asha 300 software update and downloads
Let us know the outcome.