Encoding.Unicode - это UTF-16, который использует 2 байта для кодирования всех символов. Символы ASCII (английские символы) одинаковы в UTF-8 (отдельные байты, одинаковые значения), поэтому может быть, поэтому он работает.
Я предполагаю, что командная оболочка Windows не полностью поддерживает Unicode. Забавно, что графический интерфейс Powershell 2 поддерживает UTF-16 (насколько я знаю), но программа выдает там то же исключение.
Работает следующий код, который показывает, что объект Console может перенаправлять свои выходные данные и поддерживать Encoding.Unicode:
FileStream testStream = File.Create("test.txt");
TextWriter writer = new StreamWriter(testStream, Encoding.Unicode);
Console.SetOut(writer);
Console.WriteLine("Hello World: \u263B"); // unicode smiley face
writer.Close(); // flush the output