Originally described by Thomas Glörfeld here: http://www.glorf.it/blog/2008/05/16/sql-talk/sql-server-is-not-aware-of-nondeterministic-functions.
Suppose you define a table expression (derived table, CTE, view, inline TVF) based on a query that invokes the NEWID function (call it T2). You join the table expression with another table (call it T1). The relationship between T2 and T1 is 1:M. You join T1 and T2. Depending on the join algorithm chosen by the optimizer, you might get the NEWID function to be invoked once per each result row instead of once per each T2 row.
This bug appears in SQL Server 2005, and seems like a regression from SQL Server 2000.