Files deleted from SD card are restored after restart
Clear the cache on your  File Manager,  the browser you used to download the movies, and for the application  involved used to play the movies.

For each of those applications select the application and clear its cache:

Settings > Applications > Manage Applications > All (at the top) > {application} > Clear Cache