どうも Process.BeginOutputReadLine/BeginErrorReadLineでエラーが起きることがある。調べたところ、.NETのバグっぽい。.NET2.0でも、.NET3.5でも発生するので、Issueとして登録されていない気がする。
プロセスの出力(byte)は、指定されたエンコーディングで、文字化されるが、2バイト文字圏では、たとえば、1バイトしか出力されないと文字化しようがない場合があるが、その場合の処理が抜けているのではないだろうか?
具体的には、AsyncStreamReader(非公開)のGetLinesFromStringBuilderで、

if (this.sb[length - 1] == '\r')

といった処理があるのだが、

if (length > 0 && this.sb[length - 1] == '\r')

と、しなければならない。
Workaroundとしては、ちょっと複雑だが、
・AsyncStreamReaderを自作
・Process.WaitForExitも自作関数で代用(リフレクション必須)
・ProcessWaitHandleも必要。ほかにWin32のNativeMethodあたりもいくつか。
とすることで回避できるようだ。