When dealing with unpredictable image - background relationships (complex background images, background colors that will change or images in layers that move across an inconsistent background) you will need to use a transparent gif. In this case, take special care that your transparent gifs do not have a fringe.

Other than careful, magnified touch up, exporting using the Photoshop 89A export feature is the best method. If you are working with an image that has a limited color palette you can reduce the colors when converting the mode to index to get rid of unwanted fringe colors.

Made transparent not using export89A

Using 89A export feature How to do it

Converting to RGB then back to Index mode, choosing adaptive palate and then reducing colors or fixing by hand

courst outline