Hice la siguiente "simulación":

byte[] b = new byte[256];

for (int i = 0; i < 256; i ++) {
    b[i] = (byte) (i - 128);
}
byte[] transformed = new String(b, "cp1251").getBytes("cp1251");

for (int i = 0; i < b.length; i ++) {
    if (b[i] != transformed[i]) {
        System.out.println("Wrong : " + i);
    }
}

porcp1251 esto genera solo un byte incorrecto, en la posición 25.
porKOI8-R - todo muy bien.
porcp1252 - 4 o 5 diferencias.

¿Cuál es la razón de esto y cómo se puede superar?

Sé que lo esincorrecto representar matrices de bytes como cadenas en cualquier codificación, pero es un requisito del protocolo de un proveedor de pagos, por lo que no tengo otra opción.

Actualizar: representándolo enISO-8859-1 funciona, y lo usaré parabyte[] parte, ycp1251 para la parte textual, por lo que la pregunta solo queda por curiosidad