Hi, I see you have put your images on a good diet. I’m not sure how you resize with paint? I got the same as you results as you when I tried. (Strange)
But you can use PIXresizer, (link on 1st post) or if you have it on your machine, Microsoft Office Picture Manager is fine for this. (Should be in the MS area).
The only thing with resizing your images is that you should resize with the view of keeping the aspect ratio of the image to stop the image looking distorted or stretched.
I am not sure if you have the original? But using one of the 2 programs above you should be able to resize ok. Other wise it will look like these 2 below. (I used your one on site).
360x480 STRECHED BUT DISTORTED
360x356 keeping aspect.
The other thing that will help! Is when you create a gallery, check the create thumbnail box. It will automatically reduce the kbs of the thumbnails by about 2/3rds.
Oh! I don’t believe cache has anything to do with publishing.
Cheers.