[h1dd3n]

Неправильный подход у тебя.

Тебе нужна очередь в которую сообщение будет при отправке добавляться, и отдельный асинхронный воркер который будет забирать из очереди и отправлять.

И отдельный асинхронный воркер, проще всего в отдельном потоке запилить.



ConcurrentQueue

Где-то в коде:

private void Initialize() {
	this._queue = new ConcurrentQueue<NetMessage>();

	var asyncWorker = new Thread(SomeWorker);
	asyncWorker.Start();
}

public void Send(NetMessage msg) {
	if (msg.sended) throw new InvalidOperationException("Message already sended!");

	msg.sended = true;

	this._queue.Enqueue(msg);
}

private void SomeWorker() {
	while (true) {
		NetMessage msg;
		while (!this._queue.TryDequeue(out msg)) {
			
		}

                NetworkStream.Write(nextMessage.data, 0, nextMessage.Size + NetMessage.HeaderSize);
	}
}

Кстати, какая у тебя целевая платформа ? Если .NET 4.5, то советую вместо BeginWrite/EndWrite использовать await WriteAsync.