A higher palette resolution would, as you say, increase the amount of space taken by the message, but would result in a higher fidelity of the image.
You'd need a modified interpreter, though, but by picking different values for the BF instructions, spaced further apart in the 0-255 range, you'd get less collisions (incorrect BF tokens appearing at the wrong spot in your stream).
Another possibility would be to pick different code points for each image/message encoded. Though you'd need another channel to specify which 8 bytes encode for which BF tokens. You could even not specify it, but limit the choices for the 8 byte values and try all combinations, then see which ones decode to a string that comes closest to character distribution in English language (this is the same method used by online translators to determine source language, character distribution is highly distinctive).