All these suggestions do not really make it anywhere near impossible to break though.

My proposition is rather tricky and consists of two parts.. first you allocate a number of multiple palette entries to slight variations of the same color. Then you use these colors to form dithered colors, like red and green pixels forming a yellow shape, using different red palette indexes for each red pixel at random (and same for green - or whatever other color). If the background and foreground color share some dithering component (say, there's green pixels in both the background and the foreground), the contours of symbols are "washed out" a bit and the contrast between back- and foreground is low, you get a pretty much unsurmountable obstacle for OCR at least in its current form.