Low cardinality estimate in hash match operator
The question of why one cardinality estimation model produces closer results than the other in this case is actually not that interesting. The original CE estimates that not finding a matching row has a very small probability; the new CE calculates that it is almost certain. Both are 'correct', just based on different modelling assumptions. Fundamentally, multi-column semi joins are tricky to evaluate based on single-column statistical information.

It is much more interesting to think about what the query is trying to do, and how we can write it in a way that is more compatible with the statistical information available to SQL Server.

A key observation is that the query will return row(s) with one value per group. In the case of the original query, that is row(s) with the minimum HistoryId value for each Transactionid. In the repro, it is row(s) with the minimum c1 value for each different value of c2. The NOT EXISTS query is just one way of expressing that requirement.

SQL Server has good statistical information about distinct values (density) so all we need to do is write the query in a way that makes it clear we want one value per group. There are many ways to do this, for example (using your repro):

SELECT * 
FROM dbo.nat AS N
WHERE N.c1 =
(
    SELECT MIN(N2.c1) 
    FROM dbo.nat AS N2
    WHERE N2.c2 = N.c2
);


or, equivalently:

SELECT N.* 
FROM dbo.nat AS N
JOIN
(
    SELECT 
        N.c2,
        MIN(N.c1) AS c1
    FROM dbo.nat AS N
    GROUP BY 
        N.c2
) AS J
    ON J.c2 = N.c2
    AND J.c1 = N.c1;


This produces an exactly correct estimate of 9999 rows in 2008 R2, 2012, and 2014 (both CE models):



With a natural index (which would probably be unique as well):

CREATE INDEX i ON dbo.nat (c2, c1);


The plan is even simpler:



You may not always be able to get this very simple plan form, depending on indexes, and other factors. The point I am making is that using basic grouping and joining operations often gets better results from the optimizer (and its cardinality estimation component) than more complex alternatives.

Final notes to clear some misconceptions in the question: the 'new CE' was introduced in 2014. TF 4199 enables plan-affecting optimizer fixes. TF 9481 specifies the original ('legacy') CE, and is only effective on 2014 and later versions.