As long as the paint program supports layers, you'll be fine. You _could_ do it with a program that doesn't, but it would be soo much more time consuming, not to mention essentially uneditable. In so far as it's much, much easier to change a layer or add a new one than it is to redraw part of your raster image.
AFAIK photoshop's always been cool with layers, new releases just add new functions and enhancements to the workflow. An old version would be fine. Can't comment on PSP though, mine's from '98 and it doesn't handle layers.
Just found a FREE program that supports layers, and appears quite similar to PS in the screenshots. May have to give it a go, since my pc went down last nite and I don't have the photoshop disc here. You can find it here, PAINT.NET download page