If you haven't done so already, I'd recommend using Cave Editor to remove the requirement for copyrighted bitmaps and change the image reader to read .bmp files instead of .pbm. By default, doukutsu.exe reads for the string "(C)Pixel" at the end of its .pbm files, and spits out an error if that string isn't found. You can remove this requirement via Cave Editor's
Game Settings option:

Once you've done both steps, it automatically changes all the .pbm files in the data folder to bitmaps and you can use 24-bit bitmaps however you like without restricting pallette limits.
There's also a load of other neat stuff you can do to cave story through Cave Edit and hex editors, like changing the game font to something nicer.