It's down to an optimisation introduced in SQL Server2005 often called "Deferred expression evaluation". Here's a great article by Paul White to add to others already posted.

The original "failing" query can be modified so that the calculation is written as a row-level CROSS APPLY:

WITH bbb AS (

SELECT TOP 3 x.RandomRow

FROM AAA

CROSS APPLY (SELECT RandomRow = ABS(checksum(newid())) % 6 + 1) x

ORDER BY RowNumber)

SELECT a.Col1, bbb.RandomRow

FROM AAA AS a

JOIN bbb

ON a.RowNumber = bbb.RandomRow;

The execution plan is identical to Query No 1:

Changing the CROSS APPLY to an OUTER APPLY

WITH bbb AS (

SELECT TOP 3 x.RandomRow

FROM AAA

OUTER APPLY (SELECT RandomRow = ABS(checksum(newid())) % 6 + 1) x

ORDER BY RowNumber)

SELECT a.Col1, bbb.RandomRow

FROM AAA AS a

JOIN bbb

ON a.RowNumber = bbb.RandomRow;

is sufficient to prevent the optimiser from implementing deferred expression evaluation and it generates a completely different plan where RandomRow is evaluated prior to the join between the CTE and the table:

With RandomRow evaluated prior to the join, it's now available to use as a join predicate and the query returns the expected results.