I ran a quick check, and it looks like a reasonably even distribution to me. I genenerated 2M NewId values, as follows:
SELECT NewID() AS RandomColumn INTO #t FROM Data.TableWith2Mrows
I looked at the distribution into 256 buckets, considering the first byte of the value only. All 256 buckets had values:
SELECT COUNT(*) AS Cnt
FROM (
SELECT SUBSTRING(RandomColumn,1,1) AS FirstByte, COUNT(*) AS Frequency
FROM (SELECT CAST(RandomColumn AS BINARY(16)) AS RandomColumn FROM #t) AS t
GROUP BY SUBSTRING(RandomColumn,1,1)
) AS Distribution
-----------
256
and the number of values in all the buckets was between 7200 and 7700:
SELECT COUNT(*) AS Cnt, Frequency
FROM (
SELECT SUBSTRING(RandomColumn,1,1) AS FirstByte, COUNT(*) AS Frequency
FROM (SELECT CAST(RandomColumn AS BINARY(16)) AS RandomColumn FROM #t) AS t
GROUP BY SUBSTRING(RandomColumn,1,1)
) AS Distribution
GROUP BY Frequency
ORDER BY Frequency
After I had posted this, Simon Sabin told me that he also posted a similar script. He did it four years ago. Somehow I failed to google it up:
http://sqlblogcasts.com/blogs/simons/archive/2005/06/13/Random-number-on-a-per-row-basis.aspx