If the redirect is working correctly the files don't need to exist in the old location.
ie if you are doing a 301 redirect from:
www.mysite.com/document.pdf
to
www.mysite.com/Data/Sites/1/documents/document.pdf
then if the redirect is actually working the file does not need to exist at
www.mysite.com/document.pdf
So the question is only whether you can get the redirect working or not.
Using the IIS Url Rewrite module you should be able to do it.
Or if you're trying the way Jamie showed you with web.config you may also need to have this attribute on the modules element
<modules runAllManagedModulesForAllRequests="true">
in the system.webserver section
Hope that helps,
Joe