Make the image in 16 million colours, and then when you are done, convert it to 256 colours using an optimised pallete. If you have a graphics program worth the CDs it came on, the results will be visually indistinguishable.
You see, the image itself may only be 256 colours, but those 256 colours can be any 256 colours at all[/b]. We are not confined to only using 256 colours in total in FS2, but rather of the 16 million colours we can use, 256 of them can be put into any one image, and no two images need to have the same 256.
So actually it won't do much to improve the visuals at all. It will just increase files sizes and processing time for no good purpose.