Can you do this manually?
Photoshop would make this a snap. Download your images to a directory, create a temp destination directory, run a batch action on it, check them all out, if it's all good, upload them to the original directory.
A *big deal* with a lot of WP themes I see are thumbnails, many themes/sites use the original huge image scaled down. This may take a different approach if this is the problem you're facing. It shouldn't be too bad though, you'd put your scaled down images in a directory of it's own on your server and point the requests to that directory instead of the full sized ones.