This is an interesting discovery. Well, interesting if you're into subtitle arcana, I guess. So, subtitles for HD formats are 8-bit images with full alpha transparency. Subtitles for DVD can have 3 colors and 1 fully transparent color, and no alpha channel. This is why subtitles for DVD look like, well, crap.

So in the process of upscaling my 720p subtitles to 1080p, I've been doing some processing to make them look better (just sharpening, really), but the result is always 8 bits with full transparency so I figure I'm good, right?

Except I'm not. Some software reads the subtitles based on the images just fine, but some other software simply doesn't like some of the images. It turns out that if I look at my known good (monochrome) subtitles, they always use the exact same palette of 125 colors, including transparency. If I remap one of my bad images to this new palette, the compatibility problem goes away (and with 124 shades of gray available, it doesn't look any different at all). Could this be the subtitle equivalent of a web-safe palette? (also, the palette may very well be larger than 125 colors if you include non-grayscale colors)

Who knows, but at least I've solved this weird bug. But it also exposes that, as far as I can tell, HD subtitles can't necessarily use their full 8-bits of color--not even quite 7 bits, really, and only using very specific values at that. But as it turns out, that's still quite enough for subtitles IMO.