It's certainly not a bitrate issue. That video's average is 544 kbps, far away from HQ's 2048.
I believe what you're seeing is the conversion from RGB to
YV12 colour space which is a way to lower colour resolution and thus save on the bitrate. Compare 4:4:4 (RGB) to 4:2:0 (YV12) in the following pic:

This can be noticeable on 16-bit style games. Unfortunately there's nothing you can do about it. All modern codecs use the YV12 colour space.
btw, it's rare that someone complains about this, you have good eyes.
