Whatever you do, don't try to write to the card using any utility. Only use one designed to read from it and save the recovered files to another drive.
Try PhotoRec. It's a free Open Source tool to recover a number of file types and it's available for multiple platforms, including Windows. It's a command line utility (no nice Graphical User Interface, since it's designed to work on multiple Operating Systems).
It ignores the file system entirely, and tries to reconstruct files based on headers it can find. So, it can work with severely corrupted media (not your issue since you only deleted it, but give it a go anyway if your movie file type is listed). Deleted files are usually easier to recover. But, I have no experience trying to use it with video (I've never used the movie modes on cameras I've owned with it, other than a quick test to see if they worked).
Here are the file types it can recognize:
http://www.cgsecurity.org/wiki/File_...ed_By_PhotoRec
Here's another utility you may want to look at:
http://www.pcinspector.de/file_recovery/uk/welcome.htm
In a commercial (not free) product, try PhotoRescue. They have a demo version you can download to see if it works before you buy it:
http://www.datarescue.com/photorescue/
There are more recovery utilities available, too. Here are some of them:
http://www.steves-digicams.com/digsoftware_utils.html