TaskFactory factory = new TaskFactory();
CancellationTokenSource cancellationTokenSource = new CancellationTokenSource((int) WaitTimeout);
CancellationToken cancellationToken = cancellationTokenSource.Token;

// Теперь пробегаемся по всему списку клиентов.
// Важно: если будем в цикле анализировать длину очереди, это не поможет, тк очередь постоянно пополняемая, и будет зацикливание
int iterationCount = _connectionQueue.Count;
for (int i = 0; i < iterationCount; i++)
{
	KeyValuePair<Guid, ConnectionInfo> currentConnectionInfo;
	if (_connectionQueue.TryDequeue(out currentConnectionInfo))
	{
		factory
			.StartNew(
				stateObject => ProcessConnection(stateObject),
				new Tuple<CancellationToken, KeyValuePair<Guid, ConnectionInfo>>(cancellationToken, currentConnectionInfo),
				cancellationToken)
			.ContinueWith(       // тонкий момент: обратно в очередь закидываем только после УСПЕШНОГО окончания предыдущего таска, что обеспечивается TaskContinuationOptions.OnlyOnRanToCompletion
				previouseTask => _connectionQueue.Enqueue(previouseTask.Result), 
				TaskContinuationOptions.OnlyOnRanToCompletion);
	}
}



private KeyValuePair<Guid, ConnectionInfo> ProcessConnection(object stateObject)
{
	var typedState = (Tuple<CancellationToken, KeyValuePair<Guid, ConnectionInfo>>)stateObject;

	var token = typedState.Item1;
	var info = typedState.Item2.Value;

	try
	{
		if (false == token.IsCancellationRequested)
		{
			...
			// Какой то код
			...
		}

		token.ThrowIfCancellationRequested();

		return {РЕЗУЛЬТАТ} ;
	}
	catch (Exception ex)
	{
		// при любых ошибках грохаем соединение
		// при этом удаление из очереди обработки не делаем, так как сообщения в очереди отсутствует
		// но из словаря нужно вручную
		DeleteConnection(info);

		throw;
	}
}