Will Time Machine store the same data twice in this situation?
No, if you move the files back to another location on the disk backed up by Time Machine, the next backup will create a new copy of these files on your backup volume. This may even occur if you put them back into the same place (because the files will get a new creation timestamp which AFAIK triggers Time Machine to create a new file on the backup drive).

What you can do though is to navigate to the folder which originally contained the movies, open Time Machine from there, navigate back in time until the movies are displayed and then delete all backed up versions of them.