I use Resize by Peter Bone.

You can get it here:
http://www.geocities.com/peter_bone_uk/resize.html

It's a small (+-0.8MB), fast and very effective software. It can run on the spot without any installation. You can drag 'n' drop the files into it easily.
I keep a copy in my USB drive all the time, and burn it together with photos into CDs to be given to friends.

And remember to set JPEG quality to 100%, unlessyou want to keep the file size small and don't mind the artefacts generated.

The disadvantage of Paint is that you can't resize many photos together in a batch. Have to do it one by one. And you can't control the jpeg quality... which means you'll lose quality (and introduce artefacts) everytime you save the file.

Not really recommended, unless as a last resort.