出力順が保証されないとイヤンと言うのなら、
Debug.Listeners.Clear();
Debug.Listeners.Add(new TextWriterTraceListener(Console.Out));
なんて微妙に変態ちっくなこともできるが。