The beauty of repainting... Is that you don't
need to purchase any program
DXTBMP is a freeware program that you need to transform your BMP files to DXT files (that's what FSX uses - I don't have FS2004 but as far as I know it should work with it).
Then, you need an image editing program.
I use photshop, but as far as I know Paint.net and Gimp should fit your needs, too.
DXTBMP is available here:
http://fly.to/mwgfx/Hope that helps