SQL Server: random number in WHERE clause

As far as I am aware, the only way to get a random value in a SELECT statement is by using the newid() function, as the random() function doesn’t generate new values for each row.

This leads to the following awkward construction to get a random number from, say 0 - 9:

abs(checksum(newid())) % 10

If I use this expression in the SELECT clause, it behaves as expected. However, if I try something like the following:

select *
from table
where abs(checksum(newid())) % 10>4;

I should have though that I would get roughly half the rows. Instead I get I get all or none of them. Apparently newid() is only evaluated once, instead of for each row.

The question is, how can I use a random number in the WHERE clause? Alternatively, what is the best way to get the results above?