Short of finding and changing them all, as you say, you might try using a redirect in your .htaccess file, assuming you're on Linux. It would look like this for the example you gave:
Code:
Redirect /pathtodocs/Johns Resume/Resume.doc http://www.domain.com/pathtodocs/John's Resume/Resume.doc
It's possible that doing this might throw phpdig into a loop, so you might want to watch it while it runs.
Let us know how it goes.