O arquivo quando deletado na verdade está sendo removido apenas o seu endereço. Com o passar do tempo e uso do dispositivo de armazenamento, os arquivos que ali estiveram e foram removidos começam a se corromper. Por isso, após apagar um arquivo, a ação para recuperá-lo terá mais chance obter êxito se feito rapidamente. Mas sei de casos de arquivos de 6 meses serem recuperados. O seu MP4 tem uma memória com um formato de sistema de alocação de arquivos FAT. Procure na internet um programa de recuperação de arquivos em FAT, recomendo o GetDATABack para FAT.