If I remember, how palette shifted colors are figured out is using 255/(width - 1) as the number of valid greyscale values for each shifted color (it doesn't shift the first color, which is always mapped to 0). That would give us 255/15 = 17. This bug would happen because FF is hitting the max value and wraps around, and #111111, which is decimal 17 in grayscale, is still with the bound [1, 18] for the first mapped color.
To solve, I would use greys in the middle of the target, so like #090909 and #F7F7F7 instead of #111111 and #FFFFFF respectively, if my logic is correct. (tbh it's been years since I wrote/looked at the code)