Eu fiz a seguinte "simulação":

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);
    }
}

Paracp1251 isso gera apenas um byte errado - na posição 25.
ParaKOI8-R - tudo bem.
Paracp1252 - 4 ou 5 diferenças.

Qual é o motivo disso e como isso pode ser superado?

Eu sei que éerrado representar matrizes de bytes como cadeias de caracteres em qualquer codificação, mas é um requisito do protocolo de um provedor de pagamentos, portanto, não tenho escolha.

Atualizar: representandoISO-8859-1 funciona, e eu vou usá-lo para obyte[] parte ecp1251 para a parte textual, então a questão permanece apenas por curiosidade