It's possible that all of your images were switched from JPG to or PNG to BMP extensions during the resize. BMP images are significantly larger than .jpg or .png.
Check your library before and after the conversion. It will show you the size of each image.
If you have photoshop it may be worth setting up an Action to automatically resize your screenshots and then update the images within your captivate project library.
Here's a tutorial I put together on how to do use actions in Photoshop if you're unfamiliar with how to do so.
I hope that helps.
Can I ask some questions, because cannot repro your problem.
Which version of CP do you use? Can you describe your workflow when downscaling? And what about the published SWF: is the size there increasing too, because that is really what will be published? How and when did you check the filesize? This last questions seems perhaps ridiculous, but I try to explain why. When cleaning the CP-library from unused objects, the effect on the filesize is not immediately visible (p.e. in Explorer). But when closing and reopening the file, the filesize gets correct (decreased).
Using CP4 myself, I did already some downscaling but did not have your issue, CP-filesize decreased as did the published SWF-size. It is indeed the best way to capture a rather complex UI, did downscaling for the same reason as you mentioned to avoid the user to scroll.
Captivate should take care of the downscaling. To keep quality loss as low as possible try to rescale always with the same width-height ratio (but I think that was the case, since you mention 75%). Did you try another percentage and have the same issue? Trying to find an explanation.