I have the same problem, I get around it by resizing (pixelwise) in Irfanview (free off the web) or photoshop, or anything else. Then saving it and opening with Paint and saving again.
For some reason opening and saving again in Paint compresses the kb dramatically without loosing definition. I would do the whole process in Paint but there is no way of telling it exactly what pixel size you want to resize to.
It's probably a long winded way about it but it works really well for me
Carolyn