Это потому, что при старте программы он выясняет в какой кодировке sys.stdout Да ты его меняешь, но он уже считает что там cp866. Поэтому придется делать руками unicode('XYZ', 'cp866').encode('baltic_encoding') и перед вызовами chcp делать через os.system
Хотя подозреваю при этом будут портится уже выведенные знаки.
