I have no englisn version of Photoshop now and it's hard for me to explain for you right method on right english . But it's here, in post#2. Well, I can try...

1) Choose a few frames of the monster, which use different colors. These frames can be from different sequences (Standing, Moving, Attack etc). Try to choose them in such way that these frames include all the possible colors of monster animation.
2) Create a new big image in Photoshop and place this "key" frames in it. Fill background with "transparent" color.
3) Go to the "Indexed Color" window. Choose Local (one of three versions, "Adaptive", for example) palette, 256 (or less) colors, Forced - No (you can use forced colors only for special "system" colors of Heroes, like transparent color or faint shadow, deep shadow, selection colors etc). Don't use other options like Transparency, Matte, Dither, Amount for indexing.
4) After the indexing go to "Image" menu and click on "Palette...". Save the resulting palette as *.ACT-file in some place.
5) And now you can use this palette for indexing every frame of your def-file. Just open image and load this palette for it. You can use also "Last Used" palette option, if you go in "Indexed Color" window.
6) Use Def Tool for best results after all .

A small tip - when indexing, Photoshop often do a "stroke" line around a monster borders with blue color. It looks like "transparent" color, but it's not (you can see this blue stroke in game). If you go in "Color Table" window you can see real transparent color - 0,255,255 (for RGB values) and "fake" - something like 2,254,254. Just replace these values with 0,255,255 and "stroke" line will be removed.