Edit: Eu originalmente pensei que isso estava relacionado ao .NET Framework 4.5. Acabou por se aplicar ao .NET Framework 4.0 também.

Há uma mudança na maneira como as cadeias são tratadas no Windows Server 2012, que estou tentando entender melhor. Parece que o comportamento de StartsWith foi alterado. O problema é reproduzível usando o .NET Framework 4.0 e 4.5.

Com o .NET Framework 4.5 no Windows 7, o programa abaixo imprime "False, t". No Windows 2012 Server, ele imprime "True, t".

internal class Program
{
   private static void Main(string[] args)
   {
      string byteOrderMark = Encoding.UTF8.GetString(Encoding.UTF8.GetPreamble());
      Console.WriteLine("test".StartsWith(byteOrderMark));
      Console.WriteLine("test"[0]);
   }
}

Em outras palavras, StartsWith (ByteOrderMark) retorna true, independentemente do conteúdo da string. Se você tiver um código que tente remover a marca de ordem de byte usando o método a seguir, esse código funcionará bem com o Windows 7, mas imprimirá "est" no Windows 2012.

internal class Program
{
  private static void Main(string[] args)
  {
     string byteOrderMark = Encoding.UTF8.GetString(Encoding.UTF8.GetPreamble());
     string someString = "Test";

     if (someString.StartsWith(byteOrderMark))
        someString = someString.Substring(1);

     Console.WriteLine("{0}", someString);
     Console.ReadKey();

  }

}

Percebo que você já fez algo errado se tiver marcadores de ordem de byte em uma string, mas estamos nos integrando ao código legado que possui isso. Eu sei que posso resolver esse problema específico fazendo algo como abaixo, mas quero entender melhor o problema.

someString = someString.Trim(byteOrderMark[0]);

Hans Passsant sugeriu usar o construtor de UTF8Encoding que me permite dizer explicitamente para emitir o identificador UTF8. Eu tentei isso, mas dá o mesmo resultado. O código abaixo difere na saída entre o Windows 7 e o Windows Server 2012. No Windows 7, imprime "Resultado: Falso". No Windows Server 2012, ele imprime "Resultado: verdadeiro".

  private static void Main(string[] args)
  {
     var encoding = new UTF8Encoding(encoderShouldEmitUTF8Identifier: true);
     string byteOrderMark = encoding.GetString(encoding.GetPreamble());
     Console.WriteLine("Result: " + "Hello".StartsWith(byteOrderMark));
     Console.ReadKey();
  }

Também testei a seguinte variante, que imprime False, False, False no Windows 7, mas True, True, False no Windows Server 2012, o que confirma sua relação com a implementação do StartsWith no Windows Server 2012.

  private static void Main(string[] args)
  {
     var encoding = new UTF8Encoding(encoderShouldEmitUTF8Identifier: true);
     string byteOrderMark = encoding.GetString(encoding.GetPreamble());
     Console.WriteLine("Hello".StartsWith(byteOrderMark));
     Console.WriteLine("Hello".StartsWith('\ufeff'.ToString()));
     Console.WriteLine("Hello"[0] == '\ufeff');

     Console.ReadKey();
  }